oj.uz

Submission #467262

# Submission time Handle Problem Language Result Execution time Memory
467262 2021-08-22T09:39:56 Z nathanlee726 Minerals (JOI19_minerals) C++14
75 / 100
 36 ms 2176 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;
	F(2*n){
		int ts=Query(i+1);
		if(ts==s){
			vb.pb(i);
		}
		else{
			va.pb(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 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 1 ms 328 KB Output is correct
3 Correct 3 ms 456 KB Output is correct
4 Correct 5 ms 612 KB Output is correct
5 Correct 10 ms 840 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 KB Output is correct
15 Correct 28 ms 2096 KB Output is correct
16 Correct 33 ms 2100 KB Output is correct
17 Correct 26 ms 1980 KB Output is correct
18 Correct 24 ms 1952 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 KB Output is correct
15 Correct 28 ms 2096 KB Output is correct
16 Correct 33 ms 2100 KB Output is correct
17 Correct 26 ms 1980 KB Output is correct
18 Correct 24 ms 1952 KB Output is correct
19 Correct 30 ms 2132 KB Output is correct
20 Correct 30 ms 2136 KB Output is correct
21 Correct 24 ms 2108 KB Output is correct
22 Correct 23 ms 1956 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 KB Output is correct
15 Correct 28 ms 2096 KB Output is correct
16 Correct 33 ms 2100 KB Output is correct
17 Correct 26 ms 1980 KB Output is correct
18 Correct 24 ms 1952 KB Output is correct
19 Correct 30 ms 2132 KB Output is correct
20 Correct 30 ms 2136 KB Output is correct
21 Correct 24 ms 2108 KB Output is correct
22 Correct 23 ms 1956 KB Output is correct
23 Incorrect 36 ms 2176 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 KB Output is correct
15 Correct 28 ms 2096 KB Output is correct
16 Correct 33 ms 2100 KB Output is correct
17 Correct 26 ms 1980 KB Output is correct
18 Correct 24 ms 1952 KB Output is correct
19 Correct 30 ms 2132 KB Output is correct
20 Correct 30 ms 2136 KB Output is correct
21 Correct 24 ms 2108 KB Output is correct
22 Correct 23 ms 1956 KB Output is correct
23 Incorrect 36 ms 2176 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 KB Output is correct
15 Correct 28 ms 2096 KB Output is correct
16 Correct 33 ms 2100 KB Output is correct
17 Correct 26 ms 1980 KB Output is correct
18 Correct 24 ms 1952 KB Output is correct
19 Correct 30 ms 2132 KB Output is correct
20 Correct 30 ms 2136 KB Output is correct
21 Correct 24 ms 2108 KB Output is correct
22 Correct 23 ms 1956 KB Output is correct
23 Incorrect 36 ms 2176 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 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 5 ms 612 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 7 ms 712 KB Output is correct
12 Correct 10 ms 920 KB Output is correct
13 Correct 9 ms 924 KB Output is correct
14 Correct 11 ms 840 KB Output is correct
15 Correct 28 ms 2096 KB Output is correct
16 Correct 33 ms 2100 KB Output is correct
17 Correct 26 ms 1980 KB Output is correct
18 Correct 24 ms 1952 KB Output is correct
19 Correct 30 ms 2132 KB Output is correct
20 Correct 30 ms 2136 KB Output is correct
21 Correct 24 ms 2108 KB Output is correct
22 Correct 23 ms 1956 KB Output is correct
23 Incorrect 36 ms 2176 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -