oj.uz

Submission #56273

# Submission time Handle Problem Language Result Execution time Memory
56273 2018-07-11T00:40:28 Z Yehezkiel ICC (CEOI16_icc) C++11
61 / 100
 217 ms 1056 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 508 KB Ok! 101 queries used.
2 Correct 10 ms 744 KB Ok! 109 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 744 KB Ok! 559 queries used.
2 Correct 62 ms 744 KB Ok! 808 queries used.
3 Correct 60 ms 744 KB Ok! 783 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 796 KB Ok! 1550 queries used.
2 Correct 217 ms 796 KB Ok! 2190 queries used.
3 Correct 168 ms 960 KB Ok! 1724 queries used.
4 Correct 166 ms 960 KB Ok! 1707 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 960 KB Ok! 1731 queries used.
2 Correct 167 ms 960 KB Ok! 1719 queries used.
3 Correct 196 ms 1056 KB Ok! 1787 queries used.
4 Correct 159 ms 1056 KB Ok! 1645 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 1056 KB Too many queries! 1793 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 1056 KB Too many queries! 1784 out of 1625
2 Halted 0 ms 0 KB -