oj.uz

답안 #225344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225344 2020-04-20T09:39:07 Z kshitij_sodani 도서관 (JOI18_library) C++17
0 / 100
 927 ms 632 KB 
#include <iostream>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

#define pb push_back
typedef long long llo;
#define a first
#define b second
int n;
vector<int> aa;
vector<int> bb;
/*
void Answer(vector<int> cc){
	for(auto j:cc)
	{	cout<<j<<" ";
	}
	cout<<endl;
}
int Query(vector<int> cc){
	for(auto j:cc){
		cout<<j<<" ";
	}
	cout<<endl;
	int xx;
	cin>>xx;
	return xx;
}*/
int ll;
void solve(int ind,int l,int r){
	//cout<<l<<" "<<r<<endl;
	if(l==r){
		ll=l;
		return;
		if(aa[l]==0){
			ll=-1;
			return ;
		}

	/*	if(ind==l){
			ll=-1;
			while(true){
				continue;
			}
		}
		else{*/
			for(int i=0;i<n;i++){
				if((ind==i or i==l)){

					bb[i]=1;
				}
				else{
					bb[i]=0;
				}
			}
			int yy=Query(bb);
			if(yy==1){
				aa[l]=0;
				ll=l;
			}
			else{

				ll=-1;

			}
		//}
	}
	else{
		int mid=(l+r)/2;
		int co=0;
		for(int i=0;i<n;i++){
			bb[i]=0;
		}
		for(int i=l;i<=mid;i++){
			if(aa[i]==2){
				bb[i]=1;
				co+=1;
			}
		}
		if(co==0){
			
			co=0;
				for(int i=0;i<n;i++){
					bb[i]=0;
				}
				for(int i=mid+1;i<=r;i++){
					if(aa[i]==2){
						bb[i]=1;
						co+=1;
					}
				}
				if(co==0){
					ll=-1;
					return ;
				}
				
				
				bb[ind]=1;
				int yy=Query(bb);
				bb[ind]=0;
				int zz=Query(bb);
				if(yy==zz){
					solve(ind,mid+1,r);
				}
				else{
					ll=-1;
				}

		}
		else{
			bb[ind]=1;
			int yy=Query(bb);
			bb[ind]=0;
			int zz=Query(bb);
			if(yy==zz){
				solve(ind,l,mid);
			}
			else{
				co=0;
				for(int i=0;i<n;i++){
					bb[i]=0;
				}
				for(int i=mid+1;i<=r;i++){
					if(aa[i]==2){
						bb[i]=1;
						co+=1;
					}
				}
				if(co==0){
					ll=-1;
					return ;
				}
				
				
				bb[ind]=1;
				yy=Query(bb);
				bb[ind]=0;
				zz=Query(bb);
				if(yy==zz){
					solve(ind,mid+1,r);
				}
				else{
					ll=-1;
				}
			}
		}
	}
}
void Solve(int nn){
	n=nn;
	for(int i=0;i<n;i++){
		aa.pb(2);
		bb.pb(0);
	}
	int x=0;
	deque<int> ans;
	ans.push_back(0);
	int st=0;
	int kk=0;
	int le=n-1;
	aa[0]=0;
	int cco=0;

	while(le){
		cco+=1;
		int y=x;
		ll=-2;

		solve(x,0,n-1);
		if(ll==y){
			while(true){
				continue;
			}
		}

		if(ll!=-1){
			le-=1;
		}
		if(ll==-2){
			while(true){
				continue;
			}
		}
		x=ll;

		if(x==-1){
			x=0;
			st=1;
			kk+=1;
		}
		else{
			if(st==0){
				ans.push_back(x);
			}
			else{
				ans.push_front(x);
			}
		}
		aa[x]=0;
		aa[y]=0;
	}
	vector<int> fin;
	for(int i=0;i<n;i++){
		int x=ans.front();
		ans.pop_front();
		fin.pb(x+1);
	}
	Answer(fin);
}
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	Solve(3);


	return 0;
}*/

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 256 KB # of queries: 4146
2 Incorrect 345 ms 256 KB Wrong Answer [3]
3 Correct 83 ms 256 KB # of queries: 4338
4 Correct 87 ms 256 KB # of queries: 4292
5 Incorrect 299 ms 256 KB Wrong Answer [3]
6 Correct 69 ms 384 KB # of queries: 4328
7 Correct 60 ms 256 KB # of queries: 4280
8 Incorrect 353 ms 256 KB Wrong Answer [3]
9 Correct 78 ms 384 KB # of queries: 4324
10 Incorrect 324 ms 416 KB Wrong Answer [3]
11 Correct 5 ms 256 KB # of queries: 0
12 Correct 5 ms 256 KB # of queries: 2
13 Correct 5 ms 256 KB # of queries: 8
14 Correct 5 ms 384 KB # of queries: 14
15 Correct 6 ms 416 KB # of queries: 146
16 Incorrect 304 ms 304 KB Wrong Answer [3]

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 256 KB # of queries: 4146
2 Incorrect 345 ms 256 KB Wrong Answer [3]
3 Correct 83 ms 256 KB # of queries: 4338
4 Correct 87 ms 256 KB # of queries: 4292
5 Incorrect 299 ms 256 KB Wrong Answer [3]
6 Correct 69 ms 384 KB # of queries: 4328
7 Correct 60 ms 256 KB # of queries: 4280
8 Incorrect 353 ms 256 KB Wrong Answer [3]
9 Correct 78 ms 384 KB # of queries: 4324
10 Incorrect 324 ms 416 KB Wrong Answer [3]
11 Correct 5 ms 256 KB # of queries: 0
12 Correct 5 ms 256 KB # of queries: 2
13 Correct 5 ms 256 KB # of queries: 8
14 Correct 5 ms 384 KB # of queries: 14
15 Correct 6 ms 416 KB # of queries: 146
16 Incorrect 304 ms 304 KB Wrong Answer [3]
17 Incorrect 833 ms 480 KB Wrong Answer [3]
18 Incorrect 735 ms 504 KB Wrong Answer [3]
19 Incorrect 650 ms 376 KB Wrong Answer [3]
20 Incorrect 687 ms 376 KB Wrong Answer [3]
21 Incorrect 690 ms 480 KB Wrong Answer [3]
22 Incorrect 927 ms 376 KB Wrong Answer [3]
23 Incorrect 759 ms 504 KB Wrong Answer [3]
24 Incorrect 446 ms 404 KB Wrong Answer [3]
25 Incorrect 756 ms 632 KB Wrong Answer [3]
26 Incorrect 680 ms 376 KB Wrong Answer [3]
27 Correct 231 ms 376 KB # of queries: 13134
28 Correct 503 ms 480 KB # of queries: 19932
29 Correct 499 ms 504 KB # of queries: 19910
30 Correct 536 ms 376 KB # of queries: 19932