Submission #67258

#	Time	Username	Problem	Language	Result	Execution time	Memory
67258		KLPP	Carnival (CEOI14_carnival)	C++14	0 / 100	78 ms	436 KiB

carnival

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define DEBUG 0
int n;
int arr[1000];

int pergunta(vector<int> a){
	if(DEBUG==0){
		cout<<a.size()<<" ";
		for(int i=0;i<a.size();i++)cout<<a[i]+1<<" ";
		cout<<endl;
	}
	int x;
	if(DEBUG==0){
		cin>>x;
		return x;
	}
	bool d[n];
	for(int i=0;i<n;i++)d[i]=false;
	for(int i=0;i<a.size();i++){
		d[arr[a[i]]]=true;
	}
	x=0;
	for(int i=0;i<n;i++)x+=d[i];
	return x;
}
vector<int> ans(int i, int j){
	if(i==j){
		vector<int>v;
		v.push_back(j);
		return v;
	}
	int mid=(i+j)/2;
	vector<int> v1=ans(i,mid);
	vector<int> v2=ans(mid+1,j);
	/*for(int x=0;x<v1.size();x++)cout<<v1[x]<<" ";
	cout<<"V1"<<endl;
	for(int x=0;x<v2.size();x++)cout<<v2[x]<<" ";
	cout<<"V2"<<endl;*/
	vector<pair<int,int> >V;
	int cnt[n];
	for(int x=0;x<n;x++)cnt[x]=-1;
	for(int person=0;person<v2.size();person++){
		cnt[v2[person]]=person+mid+1;
		//cout<<v2[person]<<" "<<person+mid+1<<endl;
	}
	vector<int> responde;
	for(int x=0;x<v1.size();x++){
		int cor=0;
		for(int bit=0;bit<9;bit++){vector<int> festa;
			for(int y=0;y<n;y++){
				if((y>>bit)%2==0 && cnt[y]!=-1){
					festa.push_back(cnt[y]);
				}
			}
			festa.push_back(x+i);
			int R=pergunta(festa);
			if(R==festa.size())cor+=(1<<bit);
		}
		//cout<<cor<<endl<<endl;
		if(cor<n){
			responde.push_back(cor);
		}else responde.push_back(v1[x]);
	}
	for(int person=0;person<v2.size();person++){
		responde.push_back(v2[person]);
	}
	/*for(int x=0;x<responde.size();x++)cout<<responde[x]<<" ";
	cout<<"R"<<endl;*/
	return responde;
}
int main(){
	cin>>n;
	if(DEBUG==1){
		for(int i=0;i<n;i++){
			cin>>arr[i];
			arr[i]--;
		}
	}
	vector<int> V=ans(0,n-1);
	//for(int i=0;i<V.size();i++)cout<<V[i]<<endl;
	vector<pair<int,int> > v;
	for(int i=0;i<V.size();i++){
		v.push_back(pair<int,int>(V[i],i));
	}sort(v.begin(),v.end());
	int color=0;
	int A[n];
	for(int i=0;i<v.size();i++){
		if(i==0 || v[i].first!=v[i-1].first){
			color++;
		}A[v[i].second]=color;
	}
	if(DEBUG==0){for(int i=0;i<n;i++)cout<<A[i]<<" ";
		cout<<endl;
		return 0;
	}
	bool b=true;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(arr[i]==arr[j]){
				if(A[i]!=A[j])b=false;
			}else{
				if(A[i]==A[j])b=false;
			}
		}
	}cout<<b<<endl;
	return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'int pergunta(std::vector<int>)':
carnival.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<a.size();i++)cout<<a[i]+1<<" ";
               ~^~~~~~~~~
carnival.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++){
              ~^~~~~~~~~
carnival.cpp: In function 'std::vector<int> ans(int, int)':
carnival.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int person=0;person<v2.size();person++){
                   ~~~~~~^~~~~~~~~~
carnival.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0;x<v1.size();x++){
              ~^~~~~~~~~~
carnival.cpp:61:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(R==festa.size())cor+=(1<<bit);
       ~^~~~~~~~~~~~~~
carnival.cpp:68:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int person=0;person<v2.size();person++){
                   ~~~~~~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++){
              ~^~~~~~~~~
carnival.cpp:91:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
              ~^~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20