oj.uz

Submission #467257

# Submission time Handle Problem Language Result Execution time Memory
467257 2021-08-22T09:19:20 Z nathanlee726 Minerals (JOI19_minerals) C++14
75 / 100
 36 ms 2188 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;i>=0;i--){
		Fi(j,n){
			if(i==lg-1){
				if(j&(1ll<<i)){
					s=Query(va[j]+1);
				}
			}
			else{
				if(((j&(1ll<<(i+1)))&&(j&(1ll<<(i)))==0)||((j&(1ll<<(i)))&&(j&(1ll<<(i+1)))==0)){
					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]++;
					}
					else{
						vc[vd[vc[j]/2]]++;
					}
					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]+=(1ll<<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 1 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 1 ms 328 KB Output is correct
3 Correct 3 ms 456 KB Output is correct
4 Correct 6 ms 584 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 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 32 ms 2104 KB Output is correct
16 Correct 30 ms 2124 KB Output is correct
17 Correct 22 ms 2072 KB Output is correct
18 Correct 23 ms 2044 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 32 ms 2104 KB Output is correct
16 Correct 30 ms 2124 KB Output is correct
17 Correct 22 ms 2072 KB Output is correct
18 Correct 23 ms 2044 KB Output is correct
19 Correct 30 ms 2112 KB Output is correct
20 Correct 29 ms 2152 KB Output is correct
21 Correct 29 ms 2104 KB Output is correct
22 Correct 24 ms 1916 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 32 ms 2104 KB Output is correct
16 Correct 30 ms 2124 KB Output is correct
17 Correct 22 ms 2072 KB Output is correct
18 Correct 23 ms 2044 KB Output is correct
19 Correct 30 ms 2112 KB Output is correct
20 Correct 29 ms 2152 KB Output is correct
21 Correct 29 ms 2104 KB Output is correct
22 Correct 24 ms 1916 KB Output is correct
23 Incorrect 36 ms 2188 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 32 ms 2104 KB Output is correct
16 Correct 30 ms 2124 KB Output is correct
17 Correct 22 ms 2072 KB Output is correct
18 Correct 23 ms 2044 KB Output is correct
19 Correct 30 ms 2112 KB Output is correct
20 Correct 29 ms 2152 KB Output is correct
21 Correct 29 ms 2104 KB Output is correct
22 Correct 24 ms 1916 KB Output is correct
23 Incorrect 36 ms 2188 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 32 ms 2104 KB Output is correct
16 Correct 30 ms 2124 KB Output is correct
17 Correct 22 ms 2072 KB Output is correct
18 Correct 23 ms 2044 KB Output is correct
19 Correct 30 ms 2112 KB Output is correct
20 Correct 29 ms 2152 KB Output is correct
21 Correct 29 ms 2104 KB Output is correct
22 Correct 24 ms 1916 KB Output is correct
23 Incorrect 36 ms 2188 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 328 KB Output is correct
7 Correct 3 ms 456 KB Output is correct
8 Correct 6 ms 584 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 968 KB Output is correct
13 Correct 9 ms 968 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 32 ms 2104 KB Output is correct
16 Correct 30 ms 2124 KB Output is correct
17 Correct 22 ms 2072 KB Output is correct
18 Correct 23 ms 2044 KB Output is correct
19 Correct 30 ms 2112 KB Output is correct
20 Correct 29 ms 2152 KB Output is correct
21 Correct 29 ms 2104 KB Output is correct
22 Correct 24 ms 1916 KB Output is correct
23 Incorrect 36 ms 2188 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -