kojingharangの日記

D. Colliders

12:09 |

1〜N(in [1, 10**5]) を ON か OFF にする依頼が最大 10**5 個来るので、ON になっている全ての数字が互いに素（最大公約数が１）になるように依頼を処理する問題。

すでにONまたはOFFになってたら Already on/off, ONにできないときは Conflict with ?(これがONだからONにできないという数字), 処理した場合は Success と出す。

普通にやると O(N**2) になってだめなので、ON になってる約数を map なり vector なりで管理する。Nの約数の数は(ループがsqrtN回なので) N**0.5 のオーダーなので O(N**1.5) になる。

（約数としたけどほんとは素因数で書くべきだったか。）

「約数 1 は ON になっていても conflict にしない」という処理の一部が抜けてて40分ほどずっと pretest wrong answer の原因がわからず、TLEを疑って cinをscanfに変えたりしながら７回ほど submit したが結局最後まで気づかなかった。。

（そういえばpretestでもかかった時間とメモリ量はわかるのだから、TLEじゃないことはわかったのか）

惜しくないよりはマシだけど、なんか詰めが甘い。

↓ Accepted on practice

int main() {
	int N,M;
	cin>>N>>M;
	//map<int, int> pst;
	vector<int> pst(N+1);
	vector<char> st(N);
	//scanf("\n");
	REP(i, M) {
		char si;
		int k=0;
		//scanf("%c", &si);
		//scanf("%d", &k);
		//scanf("\n");
		cin>>si>>k;
		//cout<<"------ "<<si<<" "<<k<<endl;
		if(si=='-') {
			if(st[k-1]==0) {
				cout<<"Already off"<<endl;
			} else {
				for(int v=1;v*v<=k;v++) {
					if(k%v==0) {
						pst[v]=0;
						pst[k/v]=0;
					}
				}
				cout<<"Success"<<endl;
				st[k-1]=0;
			}
		} else {
			if(st[k-1]==1) {
				cout<<"Already on"<<endl;
			} else {
				int ok=1;
				for(int v=1;v*v<=k;v++) {
					if(k%v==0) {
						if((v!=1 && pst[v]) || (k/v!=1 && pst[k/v])) {
							ok=0;
							//cout<<"Conflict with "<<pst[v]?pst[v]:pst[k/v])<<endl;          // NG
							cout<<"Conflict with "<<((v!=1 && pst[v])?pst[v]:pst[k/v])<<endl; // OK
							break;
						}
					}
				}
				if(ok) {
					for(int v=1;v*v<=k;v++) {
						if(k%v==0) {
							pst[v]=k;
							pst[k/v]=k;
						}
					}
					cout<<"Success"<<endl;
					st[k-1]=1;
				}
			}
		}
	}
	
	return 0;
}

ツイートする