oj.uz

Submission #127603

# Submission time Handle Problem Language Result Execution time Memory
127603 2019-07-09T16:13:03 Z TadijaSebez ICC (CEOI16_icc) C++11
90 / 100
 167 ms 632 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=105;
int A[N],B[N];
int Ask(vector<int> a, vector<int> b)
{
	for(int i=0;i<a.size();i++) A[i]=a[i];
	for(int i=0;i<b.size();i++) B[i]=b[i];
	return query(a.size(),b.size(),A,B);
}
int p[N],n;
int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
void init(){ for(int i=0;i<N;i++) p[i]=i;}
bool use[N];
vector<int> Extend(vector<int> a)
{
	vector<int> _a;
	for(int i=1;i<=n;i++) use[i]=0;
	for(int i:a) use[i]=1;
	for(int i=1;i<=n;i++) if(use[Find(i)]) _a.pb(i);
	return _a;
}
int AskAll(vector<int> a, vector<int> b)
{
	return Ask(Extend(a),Extend(b));
}
vector<int> Reduce1(vector<int> x, vector<int> y)
{
	while(x.size()>1)
	{
		vector<int> v[2];
		for(int i=0;i<x.size();i++) v[i&1].pb(x[i]);
		if(AskAll(v[0],y)) x=v[0];
		else x=v[1];
	}
	return x;
}
vector<int> Reduce2(vector<int> x, vector<int> y)
{
	while(x.size()>1)
	{
		vector<int> v[2];
		for(int i=0;i<x.size();i++) v[i&1].pb(x[i]);
		if(Ask(v[0],y)) x=v[0];
		else x=v[1];
	}
	return x;
}
void run(int _n)
{
	n=_n;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	init();
	for(int t=1;t<n;t++)
	{
		vector<int> root,v[2],u[2];
		for(int i=1;i<=n;i++) if(Find(i)==i) root.pb(i);
		for(int l=0;;l++)
		{
			//shuffle(root.begin(),root.end(),rng);
			for(int i=0;i<root.size();i++) use[root[i]]=(i>>l)&1;
			v[0].clear();
			v[1].clear();
			for(int i=1;i<=n;i++) v[use[Find(i)]].pb(i);
			if(Ask(v[0],v[1])) break;
		}
		//for(int i=1;i<=n;i++) if(Find(i)==i) u[use[i]].pb(i);
		//u[0]=Reduce1(u[0],u[1]);
		//u[1]=Reduce1(u[1],u[0]);
		//v[0]=Extend(u[0]);
		//v[1]=Extend(u[1]);
		v[0]=Reduce2(v[0],v[1]);
		v[1]=Reduce2(v[1],v[0]);
		setRoad(v[0][0],v[1][0]);
		Union(v[0][0],v[1][0]);
	}
}

Compilation message

icc.cpp: In function 'int Ask(std::vector<int>, std::vector<int>)':
icc.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();i++) A[i]=a[i];
              ~^~~~~~~~~
icc.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();i++) B[i]=b[i];
              ~^~~~~~~~~
icc.cpp: In function 'std::vector<int> Reduce1(std::vector<int>, std::vector<int>)':
icc.cpp:35:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<x.size();i++) v[i&1].pb(x[i]);
               ~^~~~~~~~~
icc.cpp: In function 'std::vector<int> Reduce2(std::vector<int>, std::vector<int>)':
icc.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<x.size();i++) v[i&1].pb(x[i]);
               ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<root.size();i++) use[root[i]]=(i>>l)&1;
                ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 96 queries used.
2 Correct 8 ms 504 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 504 KB Ok! 534 queries used.
2 Correct 52 ms 556 KB Ok! 672 queries used.
3 Correct 50 ms 552 KB Ok! 651 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 504 KB Ok! 1404 queries used.
2 Correct 167 ms 504 KB Ok! 1654 queries used.
3 Correct 146 ms 504 KB Ok! 1512 queries used.
4 Correct 148 ms 608 KB Ok! 1500 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 564 KB Ok! 1531 queries used.
2 Correct 151 ms 504 KB Ok! 1498 queries used.
3 Correct 161 ms 504 KB Ok! 1616 queries used.
4 Correct 148 ms 632 KB Ok! 1479 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 504 KB Ok! 1619 queries used.
2 Correct 163 ms 564 KB Ok! 1620 queries used.
3 Correct 164 ms 504 KB Ok! 1634 queries used.
4 Correct 161 ms 632 KB Ok! 1560 queries used.
5 Correct 143 ms 504 KB Ok! 1484 queries used.
6 Correct 145 ms 504 KB Ok! 1491 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 504 KB Ok! 1623 queries used.
2 Incorrect 164 ms 504 KB Too many queries! 1641 out of 1625