oj.uz

Submission #467265

# Submission time Handle Problem Language Result Execution time Memory
467265 2021-08-22T09:52:46 Z nathanlee726 Minerals (JOI19_minerals) C++14
75 / 100
 54 ms 2504 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
5 Correct 14 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 KB Output is correct
15 Correct 51 ms 2368 KB Output is correct
16 Correct 40 ms 2368 KB Output is correct
17 Correct 42 ms 2396 KB Output is correct
18 Correct 47 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 KB Output is correct
15 Correct 51 ms 2368 KB Output is correct
16 Correct 40 ms 2368 KB Output is correct
17 Correct 42 ms 2396 KB Output is correct
18 Correct 47 ms 2248 KB Output is correct
19 Correct 54 ms 2444 KB Output is correct
20 Correct 47 ms 2372 KB Output is correct
21 Correct 40 ms 2368 KB Output is correct
22 Correct 40 ms 2240 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 KB Output is correct
15 Correct 51 ms 2368 KB Output is correct
16 Correct 40 ms 2368 KB Output is correct
17 Correct 42 ms 2396 KB Output is correct
18 Correct 47 ms 2248 KB Output is correct
19 Correct 54 ms 2444 KB Output is correct
20 Correct 47 ms 2372 KB Output is correct
21 Correct 40 ms 2368 KB Output is correct
22 Correct 40 ms 2240 KB Output is correct
23 Incorrect 42 ms 2504 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 KB Output is correct
15 Correct 51 ms 2368 KB Output is correct
16 Correct 40 ms 2368 KB Output is correct
17 Correct 42 ms 2396 KB Output is correct
18 Correct 47 ms 2248 KB Output is correct
19 Correct 54 ms 2444 KB Output is correct
20 Correct 47 ms 2372 KB Output is correct
21 Correct 40 ms 2368 KB Output is correct
22 Correct 40 ms 2240 KB Output is correct
23 Incorrect 42 ms 2504 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 KB Output is correct
15 Correct 51 ms 2368 KB Output is correct
16 Correct 40 ms 2368 KB Output is correct
17 Correct 42 ms 2396 KB Output is correct
18 Correct 47 ms 2248 KB Output is correct
19 Correct 54 ms 2444 KB Output is correct
20 Correct 47 ms 2372 KB Output is correct
21 Correct 40 ms 2368 KB Output is correct
22 Correct 40 ms 2240 KB Output is correct
23 Incorrect 42 ms 2504 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 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 7 ms 660 KB Output is correct
9 Correct 14 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 12 ms 1016 KB Output is correct
13 Correct 12 ms 1096 KB Output is correct
14 Correct 15 ms 1068 KB Output is correct
15 Correct 51 ms 2368 KB Output is correct
16 Correct 40 ms 2368 KB Output is correct
17 Correct 42 ms 2396 KB Output is correct
18 Correct 47 ms 2248 KB Output is correct
19 Correct 54 ms 2444 KB Output is correct
20 Correct 47 ms 2372 KB Output is correct
21 Correct 40 ms 2368 KB Output is correct
22 Correct 40 ms 2240 KB Output is correct
23 Incorrect 42 ms 2504 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -