Submission #488043

#	Time	Username	Problem	Language	Result	Execution time	Memory
488043		PixelCat	Minerals (JOI19_minerals)	C++14	70 / 100	32 ms	2580 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
#define int LL //__int128
#define double long double
using namespace std;
using LL=long long;
using uLL=unsigned long long;
using pii=pair<LL,LL>;

#define For(i,a,b)    for(int i=a;i<=b;i++)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define Forr(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define L(id) (id*2+1)
#define R(id) (id*2+2)
#define LO(x) (x&(-x))

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1000000000000000ll) //1e15
#define EPS (1e-6)

#ifdef NYAOWO
#include "debug.hpp"
inline void USACO(const string &s) { cerr<<"USACO: "<<s<<"\n"; }

#else
#define debug(...)
inline void timer(){}
inline void USACO(const string &s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#endif

inline void NYA() { ios::sync_with_stdio(false); cin.tie(0); }
inline int gcd(int a,int b) { return __gcd(a,b); }
inline int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p,const int &mod){
	int ans=1;
	while(p){
		if(p&1) ans=ans*b%mod;
		p/=2; b=b*b%mod;
	}
	return ans;
}
int fpow(int b,int p) { return fpow(b,p,MOD); }
template<typename T> inline void chmin(T &_a,const T &_b) { if(_b<_a) _a=_b; }
template<typename T> inline void chmax(T &_a,const T &_b) { if(_b>_a) _a=_b; }
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Interactor{
	bitset<90000> bs;
	int last=0;
	void init(){
		bs.reset();
	}
	bool push(int x){
		bool ans=false;
		if(!bs[x]){
			int now=Query(x);
			bs[x]=true;
			ans=(now!=last);
			last=now;
		}
		return ans;
	}
	bool pop(int x){
		bool ans=false;
		if(bs[x]){
			int now=Query(x);
			bs[x]=false;
			ans=(now!=last);
			last=now;
		}
		return ans;
	}
	bool toggle(int x){
		int now=Query(x);
		bs[x]=!bs[x];
		bool ans=(now!=last);
		last=now;
		return ans;
	}
}inter;

void Solve(int32_t n){
	vector<int> l,r;
	For(i,1,n*2){
		if(inter.toggle(i)) r.eb(i);
		else l.eb(i);
	}
	vector<int> t(n);
	For(pos,0,15){
		int cnt=0;
		For(i,0,n-1){
			if(i&(1<<pos)) inter.push(r[i]);
			else { inter.pop(r[i]); cnt++; }
		}
		int now=0;
		For(i,0,n-1){
			if(inter.toggle(l[i])){
				t[now]=l[i];
				now++;
				l[i]=0;
				if(now==cnt) break;
			}
		}
		For(i,0,n-1) if(l[i]!=0){
			t[now]=l[i];
			now++;
		}
		assert(now==n);
		l.swap(t);
	}
	For(i,0,n-1) Answer(l[i],r[i]);
}

// void Solve(int32_t N) {
//   int v = Query(1);
//   for (int i = 1; i <= N; ++i) {
//     Answer(i, 2 * N + 1 - i);
//   }
// }

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