oj.uz

Submission #99516

# Submission time Handle Problem Language Result Execution time Memory
99516 2019-03-04T15:27:05 Z nad312 ICC (CEOI16_icc) C++17
0 / 100
 5 ms 660 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 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(l);
	setRoad(q1[0], q2[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;
			}
		}
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 660 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 640 KB Wrong road!
2 Halted 0 ms 0 KB -