oj.uz

Submission #467264

# Submission time Handle Problem Language Result Execution time Memory
467264 2021-08-22T09:50:58 Z nathanlee726 Minerals (JOI19_minerals) C++14
75 / 100
 49 ms 2520 KB 
//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include "minerals.h" 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;

//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
int Query(int x){return 0;}
void Answer(int a, int b){}
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}

vector<int> va,vb;
void Solve(int n){
	int s=0;
	int ar[2*n];
	F(2*n)ar[i]=i;
	random_shuffle(ar,ar+(2*n));
	F(2*n){
		if(s==n){
			vb.pb(ar[i]);
			continue;
		}
		int ts=Query(ar[i]+1);
		if(ts==s){
			vb.pb(ar[i]);
		}
		else{
			va.pb(ar[i]);
		}
		s=ts;
	}
	int lg=__lg(n-1)+1;
	vector<int> vc(n,0),vd(((n+1)/2),-1);
	bool vis[n*2]={0};
	for(int i=lg-1,k=0;i>=0;i--,k=1-k){
		Fi(j,n){
			if(i==lg-1){
				if(j&(1ll<<i)){
					s=Query(va[j]+1);
				}
			}
			else{
				if((((j&(1ll<<(i+1)))==0)&&((j&(1ll<<(i))))==0)||((j&(1ll<<(i)))&&(j&(1ll<<(i+1))))){
					s=Query(va[j]+1);
				} 
			}
		}
		if(i==0){
			Fi(j,n){
				if(vd[vc[j]/2]==-1){
					vd[vc[j]/2]=j;
				}
				else{
					int ts=Query(vb[j]+1);
					if(ts!=s){
						vc[j]+=(1-k);
						vc[vd[vc[j]/2]]+=k;
					}
					else{
						vc[vd[vc[j]/2]]+=(1-k);
						vc[j]+=k;
					}
					s=ts;
					Answer(va[vc[j]]+1,vb[j]+1);
					Answer(va[vc[vd[vc[j]/2]]]+1,vb[vd[vc[j]/2]]+1);
					vis[va[vc[j]]]=1;
					vis[vb[j]]=1;
					vis[va[vc[vd[vc[j]/2]]]]=1;
					vis[vb[vd[vc[j]/2]]]=1;
				}
			}
			if(n&1){
				int p=-1;
				assert(!vis[va[n-1]]);
				Fi(j,n){
					if(!vis[vb[j]])p=vb[j];
				}
				Answer(va[n-1]+1,p+1);
			}
		}
		else{
			Fi(j,n){
				int ts=Query(vb[j]+1);
				if(ts!=s)vc[j]+=(((ll)(1-k))<<i);
				else vc[j]+=(((ll)(k))<<i);
				s=ts;
			}
		}
	}
	return;	
}

/*#ifdef LOCAL
signed main(){
	IOS();
	
	return 0;
}
#endif*/

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 0 ms 264 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 664 KB Output is correct
5 Correct 15 ms 968 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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 KB Output is correct
15 Correct 40 ms 2368 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 39 ms 2404 KB Output is correct
18 Correct 40 ms 2248 KB Output is correct

Subtask #5
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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 KB Output is correct
15 Correct 40 ms 2368 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 39 ms 2404 KB Output is correct
18 Correct 40 ms 2248 KB Output is correct
19 Correct 49 ms 2440 KB Output is correct
20 Correct 42 ms 2372 KB Output is correct
21 Correct 39 ms 2488 KB Output is correct
22 Correct 48 ms 2288 KB Output is correct

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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 KB Output is correct
15 Correct 40 ms 2368 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 39 ms 2404 KB Output is correct
18 Correct 40 ms 2248 KB Output is correct
19 Correct 49 ms 2440 KB Output is correct
20 Correct 42 ms 2372 KB Output is correct
21 Correct 39 ms 2488 KB Output is correct
22 Correct 48 ms 2288 KB Output is correct
23 Incorrect 43 ms 2520 KB Wrong Answer [2]
24 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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 KB Output is correct
15 Correct 40 ms 2368 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 39 ms 2404 KB Output is correct
18 Correct 40 ms 2248 KB Output is correct
19 Correct 49 ms 2440 KB Output is correct
20 Correct 42 ms 2372 KB Output is correct
21 Correct 39 ms 2488 KB Output is correct
22 Correct 48 ms 2288 KB Output is correct
23 Incorrect 43 ms 2520 KB Wrong Answer [2]
24 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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 KB Output is correct
15 Correct 40 ms 2368 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 39 ms 2404 KB Output is correct
18 Correct 40 ms 2248 KB Output is correct
19 Correct 49 ms 2440 KB Output is correct
20 Correct 42 ms 2372 KB Output is correct
21 Correct 39 ms 2488 KB Output is correct
22 Correct 48 ms 2288 KB Output is correct
23 Incorrect 43 ms 2520 KB Wrong Answer [2]
24 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 0 ms 264 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 664 KB Output is correct
9 Correct 15 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 13 ms 1132 KB Output is correct
13 Correct 13 ms 1132 KB Output is correct
14 Correct 15 ms 968 KB Output is correct
15 Correct 40 ms 2368 KB Output is correct
16 Correct 41 ms 2392 KB Output is correct
17 Correct 39 ms 2404 KB Output is correct
18 Correct 40 ms 2248 KB Output is correct
19 Correct 49 ms 2440 KB Output is correct
20 Correct 42 ms 2372 KB Output is correct
21 Correct 39 ms 2488 KB Output is correct
22 Correct 48 ms 2288 KB Output is correct
23 Incorrect 43 ms 2520 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -