Submission #99519

#	Time	Username	Problem	Language	Result	Execution time	Memory
99519		nad312	ICC (CEOI16_icc)	C++17	100 / 100	178 ms	764 KiB

icc

#include<icc.h>
#include<bits/stdc++.h>
#define P pair<lli, lli>
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef int lli;
const lli N=109;
lli n, dd[N], cnt, a[N], b[N];
deque<lli> D[N], p[N], q1, q2, cop;

void DFS(lli u)
{
	p[cnt].push_back(u);
	dd[u]=1;
	for(auto v: D[u])
	{
		if(dd[v]==0)
		{
			DFS(v);
		}
	}
}
void Add(lli x, lli y)
{
	if(x==0)
	{
		for(auto v: p[y])
		{
			q1.push_back(v);
		}
	}
	else
	{
		for(auto v: p[y])
		{
			q2.push_back(v);
		}
	}
}
lli Ask()
{
	lli s1=q1.size(), s2=q2.size();
	for(int i=0;i<s1;i++)
	{
		a[i]=q1[i];
	}
	for(int i=0;i<s2;i++)
	{
		b[i]=q2[i];
	}
	return query(s1, s2, a, b);
}
void Solve()
{
	lli d1, d2;
	lli l=0, h=q2.size()-1;
	cop=q2;
	while(l<h)
	{
		lli mid=(l+h)/2;
		q2.clear();
		for(int i=l;i<=mid;i++)
		{
			q2.push_back(cop[i]);
		}
		if(Ask())
		{
			h=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	q2.clear();
	q2.push_back(cop[l]);
	cop=q1;
	l=0, h=q1.size()-1;
	while(l<h)
	{
		lli mid=(l+h)/2;
		q1.clear();
		for(int i=l;i<=mid;i++)
		{
			q1.push_back(cop[i]);
		}
		if(Ask())
		{
			h=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	q1.clear();
	q1.push_back(cop[l]);
	setRoad(q1[0], q2[0]);
	D[q1[0]].push_back(q2[0]);
	D[q2[0]].push_back(q1[0]);
}
void run(lli ndinh)
{
	n=ndinh;
	lli T=n-1;
	while(T--)
	{
		cnt=0;
		fill_n(&dd[0], sizeof(dd)/sizeof(dd[0]), 0);
		for(int i=1;i<=n;i++)
		{
			p[i].clear();
		}
		for(int i=1;i<=n;i++)
		{
			if(dd[i]==0)
			{
				cnt++;
				DFS(i);
			}
		}
		for(int bit=0;bit<8;bit++)
		{
			q1.clear();
			q2.clear();
			for(int i=1;i<=cnt;i++)
			{
				Add(((i>>bit)&1), i);
			}
			if(Ask())
			{
				Solve();
				break;
			}
		}
	}
}

Compilation message (stderr)

icc.cpp: In function 'void Solve()':
icc.cpp:57:6: warning: unused variable 'd1' [-Wunused-variable]
  lli d1, d2;
      ^~
icc.cpp:57:10: warning: unused variable 'd2' [-Wunused-variable]
  lli d1, d2;
          ^~

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