oj.uz

Submission #69127

# Submission time Handle Problem Language Result Execution time Memory
69127 2018-08-20T04:38:58 Z KLPP Carnival (CEOI14_carnival) C++14
0 / 100
 55 ms 528 KB 
#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==1){
		bool b[n];
		for(int i=0;i<n;i++)b[i]=false;
		for(int i=0;i<a.size();i++){
			if(b[a[i]])cout<<"ERR"<<endl;
			b[a[i]]=true;
		}
	}
	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

carnival.cpp: In function 'int pergunta(std::vector<int>)':
carnival.cpp:14:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<a.size();i++){
               ~^~~~~~~~~
carnival.cpp:21: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:31: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:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int person=0;person<v2.size();person++){
                   ~~~~~~^~~~~~~~~~
carnival.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0;x<v1.size();x++){
              ~^~~~~~~~~~
carnival.cpp:69:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(R==festa.size())cor+=(1<<bit);
       ~^~~~~~~~~~~~~~
carnival.cpp:76: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:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<V.size();i++){
              ~^~~~~~~~~
carnival.cpp:99:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size();i++){
              ~^~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 376 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 376 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 376 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 528 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 528 KB Same person came twice to the party.
2 Halted 0 ms 0 KB -