oj.uz

Submission #99519

# Submission time Handle Problem Language Result Execution time Memory
99519 2019-03-04T15:33:24 Z nad312 ICC (CEOI16_icc) C++17
100 / 100
 178 ms 764 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Ok! 95 queries used.
2 Correct 8 ms 640 KB Ok! 93 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 640 KB Ok! 528 queries used.
2 Correct 54 ms 708 KB Ok! 657 queries used.
3 Correct 49 ms 760 KB Ok! 642 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 700 KB Ok! 1373 queries used.
2 Correct 162 ms 640 KB Ok! 1596 queries used.
3 Correct 178 ms 704 KB Ok! 1596 queries used.
4 Correct 117 ms 700 KB Ok! 1474 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 764 KB Ok! 1464 queries used.
2 Correct 124 ms 640 KB Ok! 1471 queries used.
3 Correct 171 ms 640 KB Ok! 1547 queries used.
4 Correct 129 ms 640 KB Ok! 1489 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 704 KB Ok! 1553 queries used.
2 Correct 116 ms 700 KB Ok! 1521 queries used.
3 Correct 154 ms 640 KB Ok! 1571 queries used.
4 Correct 133 ms 760 KB Ok! 1540 queries used.
5 Correct 119 ms 712 KB Ok! 1455 queries used.
6 Correct 136 ms 704 KB Ok! 1534 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 736 KB Ok! 1544 queries used.
2 Correct 131 ms 736 KB Ok! 1590 queries used.