Submission #56273

#	Time	Username	Problem	Language	Result	Execution time	Memory
56273		Yehezkiel	ICC (CEOI16_icc)	C++11	61 / 100	217 ms	1056 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
const int MAXN=100;
int par[MAXN+5],n;
vector <int> kiri,kanan;
int finds(int x){
	if(par[x]!=x)
		par[x]=finds(par[x]);
	return par[x];
}
bool connected(int u,int v){
	return (finds(u)==finds(v));
}
void gabung(int u,int v){
	u=finds(u),v=finds(v);
	if(u==v)
		return;
	par[v]=u;
}
int tanya(vector <int> a,vector <int> b){
	int arr1[105];
	int arr2[105];
	for(int i=0;i<a.size();i++)
		arr1[i]=a[i];
	for(int i=0;i<b.size();i++)
		arr2[i]=b[i];
	
	return query(a.size(),b.size(),arr1,arr2);
}
void print(vector <int> arr){
	cout<<"printing arr"<<endl;
	for(int i=0;i<arr.size();i++)
		cout<<arr[i]<<" ";
	cout<<endl;
}
void perkecil(int jenis){
	vector <int> now,temp,other;
	if(jenis==0)
	{
		now=kiri;
		other=kanan;
	}
	else
	{
		now=kanan;
		other=kiri;
	}
	
	while(now.size()>1)
	{
		//assert(tanya(now,other));
		temp.clear();
		for(int i=now.size()/2;i<now.size();i++)
			temp.pb(now[i]);
		now.resize(now.size()/2);
		
		if(tanya(now,other)==0)
		{
			now=temp;
			//assert(tanya(temp,other));
		}
	}
	
	if(jenis==0)
		kiri=now;
	else
		kanan=now;
}
void findAnggota(int sisa){
	while(true)
	{
		int ambil=sisa/2;
		
		bool dikiri[105];
		for(int i=1;i<=n;i++)
			dikiri[i]=false;
		
		vector <int> anggota;
		anggota.resize(n);
		for(int i=0;i<n;i++)
			anggota[i]=i+1;
		
		random_shuffle(all(anggota));
		
		kiri.clear();
		kanan.clear();
		for(int i=0;i<n;i++)
		{
			if(dikiri[finds(anggota[i])])
				kiri.pb(anggota[i]);
			else if(ambil)
			{
				kiri.pb(anggota[i]),ambil--;
				dikiri[finds(anggota[i])]=true;
			}
			else
				kanan.pb(anggota[i]);
		}
		//print(kiri);
		//print(kanan);
		//system("pause");
		if(tanya(kiri,kanan))
			break;
	}
	//assert(tanya(kiri,kanan)==1);
}
void run(int _n){
	srand(2305);
	n=_n;
	for(int i=1;i<=n;i++)
		par[i]=i;
	
	for(int i=0;i<n-1;i++)
	{
		findAnggota(n-i);
		perkecil(0);
		perkecil(1);
		setRoad(kiri[0],kanan[0]);
		gabung(kiri[0],kanan[0]);
	}
}

Compilation message (stderr)

icc.cpp: In function 'int tanya(std::vector<int>, std::vector<int>)':
icc.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)
              ~^~~~~~~~~
icc.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();i++)
              ~^~~~~~~~~
icc.cpp: In function 'void print(std::vector<int>)':
icc.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<arr.size();i++)
              ~^~~~~~~~~~~
icc.cpp: In function 'void perkecil(int)':
icc.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=now.size()/2;i<now.size();i++)
                          ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10