제출 #433921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433921		alishahali1382	Minerals (JOI19_minerals)	C++14	90 / 100	319 ms	6900 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define SZ(x) ((int)x.size())

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, m, k, u, v, x, y, a, b, t, ans;
int mark[MAXN], shit;
set<int> On;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int Ask(int x){
	// cerr<<"Ask "<<x<<"\n";
	auto it=On.find(x);
	if (it==On.end()) On.insert(x);
	else On.erase(it);
	return ans=Query(x);
}
bool IsOn(int x){ return On.find(x)!=On.end();}
/*
void Set(vi vec){
	shit++;
	for (int x:vec){
		mark[x]=shit;
		if (!IsOn(x)) Ask(x);
	}
	vi rem;
	for (int x:On) if (mark[x]!=shit) rem.pb(x);
	for (int x:rem) Ask(x);
}*/

void divide(vi X, vi Y){
	assert(SZ(X)==SZ(Y));
	if (SZ(X)==1){
		Answer(X[0], Y[0]);
		return ;
	}
	int sz=SZ(X), mid=sz/2;
	// shuffle(all(X), rng);
	vi X1, X2, Y1, Y2;
	for (int i=0; i<sz; i++){
		if (i<mid) X1.pb(X[i]);
		else X2.pb(X[i]);
	}
	// Set(X1);
	for (int x:X1) if (!IsOn(x)) Ask(x);
	for (int x:X2) if (IsOn(x)) Ask(x);
	for (int y:Y) if (IsOn(x)) Ask(x);

	for (int y:Y){
		if (SZ(Y1)==mid) Y2.pb(y);
		else if (SZ(Y2)==sz-mid) Y1.pb(y);
		else{
			int last=ans;
			if (Ask(y)==last) Y1.pb(y);
			else Y2.pb(y);
		}
	}
	divide(X1, Y1);
	divide(X2, Y2);
}

void Solve(int _n){
	n=_n;
	vi X, Y;
	for (int i=1; i<=2*n; i++){
		int last=ans;
		if (SZ(X)==n || Ask(i)==last) Y.pb(i);
		else X.pb(i);
	}
	divide(X, Y);
}

컴파일 시 표준 에러 (stderr) 메시지

minerals.cpp: In function 'void divide(vi, vi)':
minerals.cpp:67:11: warning: unused variable 'y' [-Wunused-variable]
   67 |  for (int y:Y) if (IsOn(x)) Ask(x);
      |           ^

• 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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 10