제출 #341040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341040		ogibogi2004	ICC (CEOI16_icc)	C++14	0 / 100	1 ms	492 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
const int MAXN=128;
vector<vector<int> >comp;
int ans1,ans2,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++)
	{
		a[j-l2]=comp[i2][j];
	}
	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)
{
	int low=0,high=comp[idx1].size()-1,mid;
	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;
	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)
{
	int low=0,high=v1.size()-1,ans11,ans22,mid;
	vector<int>xd;
	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;
	}
	low=0,high=v2.size()-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;
	}
	solve(ans11,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<k;i++)
	{
		v2.push_back(v[i]);
	}
	if(ask(v1,v2))
	{
		solve(v1,v2);
		return;
	}
	v1.clear();v2.clear();
	for(int i=0;i<k;i+=2)
	{
		v1.push_back(v[i]);
	}
	for(int i=1;i<k;i+=2)
	{
		v2.push_back(v[i]);
	}
	if(ask(v1,v2))
	{
		solve(v1,v2);
		return;
	}
	v1.clear();v2.clear();
	for(int i=0;i<k;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;
}
void run(int N)
{
	n=N;
	for(int i=1;i<=n;i++)
	{
		comp.push_back({i});
	}
	for(int i=1;i<n;i++)
	{
		vector<int>vv;
		for(int j=0;j<comp.size();j++)
		{
			vv.push_back(j);
		}
		solve(vv);
		setRoad(ans1,ans2);
		add_edge(ans1,ans2);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<comp.size();i++)
      |              ~^~~~~~~~~~~~
icc.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<comp.size();i++)
      |              ~^~~~~~~~~~~~
icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>)':
icc.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=0;i<v3.size();i++)a[i]=v3[i];
      |              ~^~~~~~~~~~
icc.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=0;i<v4.size();i++)b[i]=v4[i];
      |              ~^~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:170:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  170 |  if(v.size()*2==k)k/=2;
      |     ~~~~~~~~~~^~~
icc.cpp: In function 'void run(int)':
icc.cpp:219:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |   for(int j=0;j<comp.size();j++)
      |               ~^~~~~~~~~~~~
icc.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
icc.cpp:136:7: warning: 'ans22' may be used uninitialized in this function [-Wmaybe-uninitialized]
  136 |  solve(ans11,ans22);
      |  ~~~~~^~~~~~~~~~~~~
icc.cpp:136:7: warning: 'ans11' may be used uninitialized in this function [-Wmaybe-uninitialized]
icc.cpp: In function 'void add_edge(int, int)':
icc.cpp:50:16: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |   if(i==idx1||i==idx2)continue;
      |               ~^~~~~~
icc.cpp:50:7: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |   if(i==idx1||i==idx2)continue;
      |      ~^~~~~~

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