oj.uz

답안 #514959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
514959 2022-01-18T23:19:58 Z kostia244 Minerals (JOI19_minerals) C++17
0 / 100
 14 ms 1916 KB 
#include "minerals.h"
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
bitset<90000> on;
int uwusgi(int x) {
	on.flip(x);
	return Query(x);
}
#define Query uwusgi
void Solve(int N) {
	vector<int> A, B, C(N), V(1<<16);
		mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	{
		vector<int> ord(2*N);
		iota(all(ord), 1);
		shuffle(all(ord), rng);
		int lst = 0;
		for(auto i : ord) {
			int cc = Query(i);
			(cc==lst ? B : A).push_back(i);
				
			lst = cc;
		}
	}
	// int CC = 0;
	auto AA = A;
	A.assign(1<<16, -1);
	vector<int> v(1<<16);
	iota(all(v), 0);
	// for(int b = 0; b < 16; b++) {
	// 	sort(all(v));
	// 	int lst = 0;
	// 	int i = 0;
	// 	while(i < N) {
	// 		int j = i;
	// 		while(j < N && v[j] == v[i]) j++;
	// 		for(int x = 0; i+x < j; x++)
	// 			v[i+x] |= ((x&1)^lst)<<b;//, cout << ((x&1)^lst) << ",";
			
	// 		int c = 0;
	// 		for(int p = i; p < j; p++) c += (v[p]>>b)&1;
	// 		// cout << lst << " " << c << " " << j-i+1 << endl;
	// 		if((i-j)%2 == 0) lst ^= 1;
	// 		i = j;
	// 	}
	// }
	for(int i = 0; i < 1<<16; i++) {
		V[i] = 1^(i&1);
		for(int b = 1; b < 16; b++) {
			V[i] += (i>>b)%2 != (i>>(b-1))%2;
		}
	}
	sort(all(v), [&](auto x, auto y) {
		return V[x] < V[y] ||
		(V[x] == V[y] && x < y);
	});
	for(int i = 0; i < N; i++)
		A[v[i]] = AA[i];
	B.resize(1<<16);
	for(int b = 0; b < 16; b++) {
		int lst = 0, ops = 0, done = 0;
		for(int i = 0; i < 1<<16; i++) if(A[i] != -1)
			ops += ((i>>b)&1)^on[A[i]];
		if(ops > N-ops)
		for(int i = 0; i < 1<<16; i++) if(i < (i^(1<<b)))
			swap(A[i], A[i^(1<<b)]);
		for(int i = 0; i < 1<<16; i++) if(A[i] != -1)
			if((((i>>b)&1)^on[A[i]])&&!(A[i^(1<<b)]==-1))
				lst = Query(A[i]), done++;
		// cout << ops << " " << N-ops << " " << done << endl;
		vector<int> cnt(1<<16), cnto(1<<16);
		for(auto i : C) cnt[i]++;
		for(int i = 0; i < 1<<b; i++) {
			for(int j = 0; j < 1<<(16-b); j++) {
				int c = i | (j<<b);
				if(A[c]!=-1)
					cnto[i] += j&1;
			}
		}
		for(int i = 0; i < N; i++) {
			if(!cnto[C[i]]) {cnt[C[i]]--;continue;}
			if(cnto[C[i]]) {
				int qq = -1;
				
				if(cnto[C[i]] == cnt[C[i]] && lst != qq) qq = lst;//cout << "HEY"<<endl;
				else	
				qq = Query(B[i]);
				if(lst == qq) cnto[C[i]]--;
				C[i] |= (lst == qq)<<b;
				lst = qq;
			} 
			cnt[C[i]]--;
		}
		// for(auto i : C) cout << i << " "; cout << endl;
	}
	for(int i = 0; i < N; i++)
		Answer(A[C[i]], B[i]);
 
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1916 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1864 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -