Submission #341059

#	Time	Username	Problem	Language	Result	Execution time	Memory
341059		ogibogi2004	ICC (CEOI16_icc)	C++14	61 / 100	193 ms	636 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
const int MAXN=128;
vector<vector<int> >comp;
int ans1=-1,ans2=-1,n;
bool ask(int i1,int i2)
{
	int size_a=comp[i1].size(),size_b=comp[i2].size();
	int a[size_a];
	int b[size_b];
	for(int i=0;i<size_a;i++)a[i]=comp[i1][i];
	for(int i=0;i<size_b;i++)b[i]=comp[i2][i];
	return query(size_a,size_b,a,b);
}
bool ask(int i1,int l1,int r1,int i2,int l2,int r2)
{
	int size_a=r1-l1+1;
	int size_b=r2-l2+1;
	int a[size_a],b[size_b];
	for(int j=l1;j<=r1;j++)
	{
		a[j-l1]=comp[i1][j];
	}
	for(int j=l2;j<=r2;j++)
	{
		b[j-l2]=comp[i2][j];
	}
	//cout<<"ask for:\n";
	//cout<<i1<<" "<<l1<<" "<<r1<<" "<<i2<<" "<<l2<<" "<<r2<<endl;
	//cout<<"A: ";
	//for(int i=0;i<size_a;i++)cout<<a[i]<<" ";
	//cout<<endl;
	//cout<<"B: ";
	//for(int i=0;i<size_b;i++)cout<<b[i]<<" ";
	//cout<<endl;
	return query(size_a,size_b,a,b);
}
void add_edge(int u,int v)
{
	int idx1,idx2;
	for(int i=0;i<comp.size();++i)
	{
		for(auto xd:comp[i])
		{
			if(xd==u)idx1=i;
			if(xd==v)idx2=i;
		}
	}
	vector<vector<int> >newcomp;
	newcomp.push_back(comp[idx1]);
	for(auto xd:comp[idx2])
	{
		newcomp.back().push_back(xd);
	}
	for(int i=0;i<comp.size();++i)
	{
		if(i==idx1||i==idx2)continue;
		newcomp.push_back(comp[i]);
	}
	comp=newcomp;
}
bool ask(vector<int>v1,vector<int>v2)
{
	vector<int>v3,v4;
	for(auto xd:v1)
	{
		for(auto dx:comp[xd])v3.push_back(dx);
	}
	for(auto xd:v2)
	{
		for(auto dx:comp[xd])v4.push_back(dx);
	}
	int size_a=v3.size();
	int size_b=v4.size();
	int a[size_a],b[size_b];
	for(int i=0;i<v3.size();i++)a[i]=v3[i];
	for(int i=0;i<v4.size();i++)b[i]=v4[i];
	return query(size_a,size_b,a,b);
}
void solve(int idx1,int idx2)
{
	//cout<<"solve89 "<<idx1<<" "<<idx2<<endl;
	int low=0,high=comp[idx1].size()-2,mid;ans1=high+1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ask(idx1,0,mid,idx2,0,comp[idx2].size()-1))
		{
			ans1=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	ans1=comp[idx1][ans1];
	low=0,high=comp[idx2].size()-1;ans2=high+1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ask(idx2,0,mid,idx1,0,comp[idx1].size()-1))
		{
			ans2=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	ans2=comp[idx2][ans2];
	return;
}
void solve(vector<int>v1,vector<int>v2)
{
	//cout<<"solve for:\n";
	//for(auto xd:v1)cout<<xd<<" ";
	//cout<<endl;
	//for(auto xd:v2)cout<<xd<<" ";
	//cout<<endl;
	int low=0,high=v1.size()-1,ans11=high+1,ans22,mid;
	vector<int>xd;
	//cout<<"?1\n";
	while(low<=high)
	{
		mid=(low+high)/2;
		xd.clear();
		for(int i=0;i<=mid;++i)
		{
			xd.push_back(v1[i]);
		}
		if(ask(xd,v2))
		{
			ans11=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	//cout<<"?2\n";
	low=0,high=v2.size()-1;ans2=high+1;
	while(low<=high)
	{
		mid=(low+high)/2;
		xd.clear();
		for(int i=0;i<=mid;i++)
		{
			xd.push_back(v2[i]);
		}
		if(ask(xd,v1))
		{
			ans22=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	//cout<<"?3\n";
	//cout<<ans11<<" "<<ans22<<endl;
	solve(v1[ans11],v2[ans22]);
}
void solve(vector<int>v)
{
	if(v.size()==2)
	{
		solve({v[0]},{v[1]});
	}
	if(v.size()==3)
	{
		if(ask({v[0]},{v[1],v[2]}))
		{
			solve({v[0]},{v[1],v[2]});
			return;
		}
		else solve({v[0],v[1]},{v[2]});
		return;
	}
	if(v.size()==4)
	{
		if(ask({v[0],v[1]},{v[2],v[3]}))
		{
			solve({v[0],v[1]},{v[2],v[3]});
			return;
		}
		else solve({v[0],v[2]},{v[1],v[3]});
	}
	vector<int>v1,v2;
	int m=v.size(),k=1;
	while(m)
	{
		k*=2;
		m/=2;
	}
	if(v.size()*2==k)k/=2;
	/*for(int i=0;i<k/2;i++)
	{
		v1.push_back(v[i]);
	}
	for(int i=k/2;i<v.size();i++)
	{
		v2.push_back(v[i]);
	}
	cout<<"v1:";
	for(auto ico:v1)cout<<" "<<ico;
	cout<<endl;
	cout<<"v2:";
	for(auto ico:v2)cout<<" "<<ico;
	cout<<endl;
	if(ask(v1,v2))
	{
		solve(v1,v2);
		return;
	}
	v1.clear();v2.clear();
	for(int i=0;i<v.size();i+=2)
	{
		v1.push_back(v[i]);
	}
	for(int i=1;i<v.size();i+=2)
	{
		v2.push_back(v[i]);
	}
	cout<<"v1:";
	for(auto ico:v1)cout<<" "<<ico;
	cout<<endl;
	cout<<"v2:";
	for(auto ico:v2)cout<<" "<<ico;
	cout<<endl;
	if(ask(v1,v2))
	{
		solve(v1,v2);
		return;
	}
	v1.clear();v2.clear();
	for(int i=0;i<v.size();i++)
	{
		if(i%2==0&&i>=k/2)v1.push_back(v[i]);
		if(i%2==1&&i>=k/2)v2.push_back(v[i]);
		if(i%2==1&&i<k/2)v1.push_back(v[i]);
		if(i%2==0&&i<k/2)v2.push_back(v[i]);
	}
	solve(v1,v2);
	return;*/
	for(int i=1;i<=k/2;i*=2)
	{
		v1.clear();v2.clear();
		for(int j=0;j<v.size();j++)
		{
			if(j&i)v1.push_back(v[j]);
			else v2.push_back(v[j]);
		}
		if(i==k/2||ask(v1,v2))
		{
			solve(v1,v2);
			return;
		}
	}
}
void run(int N)
{
	n=N;
	for(int i=1;i<=n;++i)
	{
		comp.push_back({i});
	}
	for(int i=1;i<n;++i)
	{
		ans1=-1;ans2=-1;
		vector<int>vv;
		for(int j=0;j<comp.size();++j)
		{
			vv.push_back(j);
		}
		solve(vv);
		if(ans1==-1&&ans2==-1)
		{
			assert(false);
		}
		//cout<<"found "<<ans1<<" "<<ans2<<endl;
		setRoad(ans1,ans2);
		add_edge(ans1,ans2);
		for(int j=0;j<comp.size();j++)
		{
			/*cout<<j<<":";
			for(auto xd:comp[j])cout<<" "<<xd;
			cout<<endl;*/
		}
		//cout<<"lol\n";
	}
}

Compilation message (stderr)

icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for(int i=0;i<comp.size();++i)
      |              ~^~~~~~~~~~~~
icc.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i=0;i<comp.size();++i)
      |              ~^~~~~~~~~~~~
icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>)':
icc.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<v3.size();i++)a[i]=v3[i];
      |              ~^~~~~~~~~~
icc.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0;i<v4.size();i++)b[i]=v4[i];
      |              ~^~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:188:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  188 |  if(v.size()*2==k)k/=2;
      |     ~~~~~~~~~~^~~
icc.cpp:241:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  241 |   for(int j=0;j<v.size();j++)
      |               ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:264:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |   for(int j=0;j<comp.size();++j)
      |               ~^~~~~~~~~~~~
icc.cpp:276:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  276 |   for(int j=0;j<comp.size();j++)
      |               ~^~~~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
icc.cpp:154:26: warning: 'ans22' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |  solve(v1[ans11],v2[ans22]);
      |                          ^
icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:58:16: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |   if(i==idx1||i==idx2)continue;
      |               ~^~~~~~
icc.cpp:58:7: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |   if(i==idx1||i==idx2)continue;
      |      ~^~~~~~

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