oj.uz

답안 #56296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56296 2018-07-11T03:09:30 Z Yehezkiel CEOI16_icc (CEOI16_icc) C++11
90 / 100
 218 ms 852 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;
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){				//O(N)
	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 expand(vector <int> &vec){		//isinya cuman kepala suku	O(N)
	bool root[MAXN+5];
	for(int i=1;i<=n;i++)
		root[i]=false;
	for(auto isi:vec)
		root[isi]=true;
	vec.clear();
	for(int i=1;i<=n;i++)
		if(root[finds(i)])
			vec.pb(i);
}
void shrink(vector <int> &vec){
	int n=0;
	for(int i=0;i<vec.size();i++)
	{
		if(par[vec[i]]==vec[i])
			vec[n++]=vec[i];
	}
	vec.resize(n);
}
void masukkan(vector <int> &tampung,const vector <int> tambahan){
	for(int isi:tambahan)
		tampung.pb(isi);
}
void perkecil(vector <int> &now,const vector <int> &other){			//O(NlogN)
	int nomor[MAXN+5],n=0;
	for(int i=0;i<now.size();i++)
	{
		if(now[i]==par[now[i]])
			nomor[now[i]]=n++;
	}
	
	vector <vector <int> > temp1,temp2;
	temp1.resize(n),temp2.resize(n);
	for(int i=0;i<now.size();i++)
		temp1[nomor[finds(now[i])]].pb(now[i]);
	
	int jawaban;
	while(true)				//O(logN)
	{
		int total=0,lebih=0;
		for(int i=0;i<n;i++)
		{
			total+=temp1[i].size();
			lebih+=temp1[i].size()%2;
		}
		if(total==1)
			break;
		lebih/=2;
		//cout<<totalnya "<<total<<endl;
		
		now.clear();
		for(int i=0;i<n;i++)
		{
			random_shuffle(all(temp1[i]));
			int ambil=temp1[i].size()/2;
			if(temp1[i].size()&1&&lebih)
				ambil++,lebih--;
			temp2[i].clear();
			for(int j=ambil;j<temp1[i].size();j++)
				temp2[i].pb(temp1[i][j]);
			temp1[i].resize(ambil);
			
			masukkan(now,temp1[i]);
		}
		if(tanya(now,other)==0)				//O(N)
		{
			for(int i=0;i<n;i++)
				temp1[i]=temp2[i];
		}
	}
	for(int i=0;i<n;i++)
	{
		if(temp1[i].size()==1)
		{
			now=temp1[i];
			return;
		}
	}
	assert(false);
}

void bagiDua(vector <int> &vec,int &lebih,vector<vector<int> > &tampung){
	random_shuffle(all(vec));
	int ambil=vec.size()/2;
	if(lebih&&(vec.size()&1))
		lebih--,ambil++;
	
	vector <int> kiri,kanan;
	for(int i=0;i<vec.size();i++)
	{
		if(i<ambil)
			kiri.pb(vec[i]);
		else
			kanan.pb(vec[i]);
	}
	tampung.pb(kiri);tampung.pb(kanan);
}
vector <int> kiri,kanan;
void findAnggota(){
	vector <vector <int> > anggota,baru;
	anggota.resize(1);
	for(int i=1;i<=n;i++)
	{
		if(par[i]==i)
			anggota[0].pb(i);
	}
	
	//cout<<"MULAI"<<endl;
	for(int loop=0;;loop++)
	{
		baru.clear();
		int lebih=0;
		for(auto &isi:anggota)
			lebih+=isi.size()%2;
		lebih/=2;
		
		int terbesar=-1;
		for(auto &isi:anggota)
		{
			terbesar=max(terbesar,(int) isi.size());
			bagiDua(isi,lebih,baru);
		}
		assert(terbesar>1);
		
		kiri.clear();kanan.clear();
		for(int i=0;i<baru.size();i++)
		{
			for(auto isi:baru[i])
			{
				if(i&1)
					kanan.pb(isi);
				else
					kiri.pb(isi);
			}
		}
		assert(lebih==0);
		//cout<<loop<<" "<<target<<" "<<(ukuran<<loop)<<" "<<lebih<<endl;
		//cout<<kiri.size()<<" "<<kanan.size()<<endl;
		assert(abs((int) kiri.size() - (int) kanan.size())<=1);
		expand(kiri),expand(kanan);
		if(tanya(kiri,kanan))
			break;
		
		anggota=baru;
	}
}
void run(int _n){
	srand(0);
	n=_n;
	for(int i=1;i<=n;i++)
		par[i]=i;
	
	for(int i=0;i<n-1;i++)
	{
		findAnggota();
		//cout<<"found"<<endl;
		perkecil(kiri,kanan);
		//cout<<"go on"<<endl;
		perkecil(kanan,kiri);
		//cout<<"the last"<<endl;
		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:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++)
              ~^~~~~~~~~
icc.cpp:27: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:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<arr.size();i++)
              ~^~~~~~~~~~~
icc.cpp: In function 'void shrink(std::vector<int>&)':
icc.cpp:51:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
icc.cpp: In function 'void perkecil(std::vector<int>&, const std::vector<int>&)':
icc.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<now.size();i++)
              ~^~~~~~~~~~~
icc.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<now.size();i++)
              ~^~~~~~~~~~~
icc.cpp:97:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=ambil;j<temp1[i].size();j++)
                    ~^~~~~~~~~~~~~~~~
icc.cpp:75:6: warning: unused variable 'jawaban' [-Wunused-variable]
  int jawaban;
      ^~~~~~~
icc.cpp: In function 'void bagiDua(std::vector<int>&, int&, std::vector<std::vector<int> >&)':
icc.cpp:127:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
icc.cpp: In function 'void findAnggota()':
icc.cpp:164:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<baru.size();i++)
               ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 504 KB Ok! 97 queries used.
2 Correct 8 ms 616 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 616 KB Ok! 534 queries used.
2 Correct 55 ms 808 KB Ok! 688 queries used.
3 Correct 54 ms 808 KB Ok! 674 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 808 KB Ok! 1423 queries used.
2 Correct 163 ms 808 KB Ok! 1679 queries used.
3 Correct 149 ms 808 KB Ok! 1494 queries used.
4 Correct 145 ms 808 KB Ok! 1521 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 808 KB Ok! 1545 queries used.
2 Correct 143 ms 808 KB Ok! 1517 queries used.
3 Correct 170 ms 808 KB Ok! 1634 queries used.
4 Correct 174 ms 808 KB Ok! 1450 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 808 KB Ok! 1620 queries used.
2 Correct 214 ms 808 KB Ok! 1651 queries used.
3 Correct 218 ms 852 KB Ok! 1659 queries used.
4 Correct 206 ms 852 KB Ok! 1626 queries used.
5 Correct 164 ms 852 KB Ok! 1476 queries used.
6 Correct 183 ms 852 KB Ok! 1561 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 852 KB Too many queries! 1634 out of 1625
2 Halted 0 ms 0 KB -