Submission #488043

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
488043	2021-11-17T13:34:03 Z	PixelCat	Minerals (JOI19_minerals)	C++14	70 / 100	32 ms	2580 KB

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.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	328 KB	Output is correct
2	Correct	2 ms	328 KB	Output is correct
3	Correct	3 ms	456 KB	Output is correct
4	Correct	6 ms	712 KB	Output is correct
5	Correct	11 ms	988 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct

Subtask #4
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct
15	Correct	27 ms	2500 KB	Output is correct
16	Correct	25 ms	2492 KB	Output is correct
17	Correct	19 ms	2580 KB	Output is correct
18	Correct	19 ms	2352 KB	Output is correct

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct
15	Correct	27 ms	2500 KB	Output is correct
16	Correct	25 ms	2492 KB	Output is correct
17	Correct	19 ms	2580 KB	Output is correct
18	Correct	19 ms	2352 KB	Output is correct
19	Incorrect	32 ms	2284 KB	Wrong Answer [2]
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct
15	Correct	27 ms	2500 KB	Output is correct
16	Correct	25 ms	2492 KB	Output is correct
17	Correct	19 ms	2580 KB	Output is correct
18	Correct	19 ms	2352 KB	Output is correct
19	Incorrect	32 ms	2284 KB	Wrong Answer [2]
20	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct
15	Correct	27 ms	2500 KB	Output is correct
16	Correct	25 ms	2492 KB	Output is correct
17	Correct	19 ms	2580 KB	Output is correct
18	Correct	19 ms	2352 KB	Output is correct
19	Incorrect	32 ms	2284 KB	Wrong Answer [2]
20	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct
15	Correct	27 ms	2500 KB	Output is correct
16	Correct	25 ms	2492 KB	Output is correct
17	Correct	19 ms	2580 KB	Output is correct
18	Correct	19 ms	2352 KB	Output is correct
19	Incorrect	32 ms	2284 KB	Wrong Answer [2]
20	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	200 KB	Output is correct
2	Correct	0 ms	200 KB	Output is correct
3	Correct	1 ms	200 KB	Output is correct
4	Correct	0 ms	200 KB	Output is correct
5	Correct	1 ms	328 KB	Output is correct
6	Correct	2 ms	328 KB	Output is correct
7	Correct	3 ms	456 KB	Output is correct
8	Correct	6 ms	712 KB	Output is correct
9	Correct	11 ms	988 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	7 ms	884 KB	Output is correct
12	Correct	10 ms	1044 KB	Output is correct
13	Correct	10 ms	1096 KB	Output is correct
14	Correct	7 ms	1008 KB	Output is correct
15	Correct	27 ms	2500 KB	Output is correct
16	Correct	25 ms	2492 KB	Output is correct
17	Correct	19 ms	2580 KB	Output is correct
18	Correct	19 ms	2352 KB	Output is correct
19	Incorrect	32 ms	2284 KB	Wrong Answer [2]
20	Halted	0 ms	0 KB	-

Submission #488043

Compilation message