Submission #262062

#	Time	Username	Problem	Language	Result	Execution time	Memory
262062		patrikpavic2	Minerals (JOI19_minerals)	C++17	80 / 100	166 ms	56956 KiB

minerals

#include "minerals.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;

const int N = 1e5 + 500;

int kod[N], tp[N], P[N], ans[N], izb[N];
int un[N], lst = 0, mks = 0, n;
vector < int > kol[20][N];

int pitaj(int x){
	int nw = Query(x);
	int ret = abs(lst - nw);
	lst = nw; un[x] = !un[x];
	return ret;
}

void pripremi(int l, int r, int raz){
	if(l == r) return;
	mks = max(mks, raz);
	for(int i = l;i <= (l + r) / 2;i++)
		kod[i] += (1 << raz);
	pripremi(l, (l + r) / 2, raz + 1);
	pripremi((l + r) / 2 + 1, r, raz + 1);
}

void odradi(int red){
	for(int i = 1;i <= 2 * n;i++){
		if(!izb[i] && !tp[i] && (un[i] ^ (!!(P[i] & (1 << red)))))
			pitaj(i);
	}
	for(int i = 1;i <= 2 * n;i++)
		if(tp[i] && !ans[i]){
			int odg = !pitaj(i);
			P[i] += odg * (1 << red);
		}
}

inline void mozda(int red){
	for(int i = 2 * n;i >= 1;i--){
		if(!tp[i] || ans[i]) continue;
		while(izb[kol[red][P[i]].back()]) kol[red][P[i]].pop_back();
		//printf("i = %d P[i] = %d kol = %d\n", i, P[i], (int)kol[red][P[i]].size());
		if(kol[red][P[i]].size() == 1 || (kol[red][P[i]][(int)kol[red][P[i]].size() - 2] < i)){
			ans[i] = *lower_bound(kol[red][P[i]].begin(), kol[red][P[i]].end(), i);
			izb[ans[i]] = 1;
		//	printf("nasao\n");
		}
	}
	for(int i = 1;i <= 2 * n;i++){
		if(!tp[i] || ans[i]) continue;
		while(izb[kol[red][P[i]].back()]) kol[red][P[i]].pop_back();
		//printf("i = %d P[i] = %d kol = %d\n", i, P[i], (int)kol[red][P[i]].size());
		if(kol[red][P[i]].size() == 1 || (kol[red][P[i]][(int)kol[red][P[i]].size() - 2] < i)){
			ans[i] = kol[red][P[i]].back();
			izb[ans[i]] = 1;
		//	printf("nasao\n");
		}
	}		
	
}

bool cmp(int x, int y){
	return P[x] < P[y];
}

void Solve(int nn) {
	n = nn; 
	pripremi(0, n - 1, 0);
	int cur = 0;
	for(int i = 1;i <= 2 * n;i++){
		tp[i] = pitaj(i);
		if(!tp[i]){
			P[i] = kod[cur++];
			for(int j = 0;j <= mks + 1;j++)
				kol[j][P[i] & ((1 << j) - 1)].PB(i);
		}
	}
	mozda(0); mozda(0); mozda(0);
	for(int i = 0;i <= mks;i++){
		odradi(i);
		mozda(i + 1); mozda(i + 1); mozda(i + 1);
	}
	for(int i = 1;i <= 2 * n;i++){
		//if(tp[i]) printf("%d %d\n", i, ans[i]);
		if(tp[i]) Answer(i, ans[i]);
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10