oj.uz

답안 #467263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467263 2021-08-22T09:42:12 Z nathanlee726 Minerals (JOI19_minerals) C++14
75 / 100
 34 ms 2172 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){
		if(s==n){
			vb.pb(i);
			continue;
		}
		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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 5 ms 712 KB Output is correct
5 Correct 10 ms 840 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct
15 Correct 27 ms 2124 KB Output is correct
16 Correct 32 ms 2132 KB Output is correct
17 Correct 22 ms 2044 KB Output is correct
18 Correct 28 ms 1908 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct
15 Correct 27 ms 2124 KB Output is correct
16 Correct 32 ms 2132 KB Output is correct
17 Correct 22 ms 2044 KB Output is correct
18 Correct 28 ms 1908 KB Output is correct
19 Correct 34 ms 2172 KB Output is correct
20 Correct 30 ms 2112 KB Output is correct
21 Correct 22 ms 2092 KB Output is correct
22 Correct 23 ms 1980 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct
15 Correct 27 ms 2124 KB Output is correct
16 Correct 32 ms 2132 KB Output is correct
17 Correct 22 ms 2044 KB Output is correct
18 Correct 28 ms 1908 KB Output is correct
19 Correct 34 ms 2172 KB Output is correct
20 Correct 30 ms 2112 KB Output is correct
21 Correct 22 ms 2092 KB Output is correct
22 Correct 23 ms 1980 KB Output is correct
23 Incorrect 29 ms 2168 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct
15 Correct 27 ms 2124 KB Output is correct
16 Correct 32 ms 2132 KB Output is correct
17 Correct 22 ms 2044 KB Output is correct
18 Correct 28 ms 1908 KB Output is correct
19 Correct 34 ms 2172 KB Output is correct
20 Correct 30 ms 2112 KB Output is correct
21 Correct 22 ms 2092 KB Output is correct
22 Correct 23 ms 1980 KB Output is correct
23 Incorrect 29 ms 2168 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct
15 Correct 27 ms 2124 KB Output is correct
16 Correct 32 ms 2132 KB Output is correct
17 Correct 22 ms 2044 KB Output is correct
18 Correct 28 ms 1908 KB Output is correct
19 Correct 34 ms 2172 KB Output is correct
20 Correct 30 ms 2112 KB Output is correct
21 Correct 22 ms 2092 KB Output is correct
22 Correct 23 ms 1980 KB Output is correct
23 Incorrect 29 ms 2168 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 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 1 ms 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 712 KB Output is correct
9 Correct 10 ms 840 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 8 ms 712 KB Output is correct
12 Correct 23 ms 880 KB Output is correct
13 Correct 10 ms 968 KB Output is correct
14 Correct 11 ms 872 KB Output is correct
15 Correct 27 ms 2124 KB Output is correct
16 Correct 32 ms 2132 KB Output is correct
17 Correct 22 ms 2044 KB Output is correct
18 Correct 28 ms 1908 KB Output is correct
19 Correct 34 ms 2172 KB Output is correct
20 Correct 30 ms 2112 KB Output is correct
21 Correct 22 ms 2092 KB Output is correct
22 Correct 23 ms 1980 KB Output is correct
23 Incorrect 29 ms 2168 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -