# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
223471 |
2020-04-15T09:45:02 Z |
MKopchev |
ICC (CEOI16_icc) |
C++14 |
|
246 ms |
572 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
const int nmax=100+42;
/*
void setRoad(int a,int b)
{
cout<<"set "<<a<<" "<<b<<endl;
}
int query(int size_a,int size_b,int a[],int b[])
{
cout<<"size_a "<<size_a<<" a ";for(int i=0;i<size_a;i++)cout<<a[i]<<" ";cout<<endl;
cout<<"size_b "<<size_b<<" b ";for(int i=0;i<size_b;i++)cout<<b[i]<<" ";cout<<endl;
int ret;
cin>>ret;
return ret;
}
*/
int size_a,size_b,a[nmax],b[nmax];
int n;
int parent[nmax];
int root(int node)
{
if(node==parent[node])return parent[node];
parent[node]=root(parent[node]);
return parent[node];
}
int my_ask(vector<int> lhs,vector<int> rhs)
{
size_a=lhs.size();
for(int i=0;i<size_a;i++)
a[i]=lhs[i];
size_b=rhs.size();
for(int i=0;i<size_b;i++)
b[i]=rhs[i];
return query(size_a,size_b,a,b);
}
vector<int> in[nmax];
mt19937 rng(1337);
void my_merge(int u,int v)
{
setRoad(u,v);
int le=root(u),ri=root(v);
for(auto k:in[ri])
in[le].push_back(k);
in[ri]={};
parent[ri]=le;
}
void my_reduce(vector<int> &to_reduce,vector<int> other)
{
while(to_reduce.size()>1)
{
vector<int> help[2];
help[0]={};
help[1]={};
for(int i=0;i<to_reduce.size();i++)
help[i%2].push_back(to_reduce[i]);
if(my_ask(help[0],other))to_reduce=help[0];
else to_reduce=help[1];
}
}
void run(int N)
{
n=N;
for(int i=1;i<=n;i++)parent[i]=i,in[i]={i};
for(int road=1;road<n;road++)
{
vector<int> lhs={};
vector<int> rhs={};
while(1)
{
lhs={};
rhs={};
int in_lhs=0,in_rhs=0;
for(int i=1;i<=n;i++)
if(rng()%2==0)
{
for(auto w:in[i])lhs.push_back(w);
in_lhs++;
}
else
{
for(auto w:in[i])rhs.push_back(w);
in_rhs++;
}
if(lhs.size()==0||rhs.size()==0)continue;
if(abs(in_lhs-in_rhs)>1)continue;
if(in_lhs!=in_rhs&&(in_lhs+in_rhs)%2==0)continue;
if(my_ask(lhs,rhs))break;
}
my_reduce(lhs,rhs);
my_reduce(rhs,lhs);
int u=lhs[0],v=rhs[0];
my_merge(u,v);
}
}
/*
int main()
{
run(4);
}
*/
Compilation message
icc.cpp: In function 'void my_reduce(std::vector<int>&, std::vector<int>)':
icc.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<to_reduce.size();i++)
~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
512 KB |
Ok! 103 queries used. |
2 |
Correct |
11 ms |
512 KB |
Ok! 102 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
512 KB |
Ok! 537 queries used. |
2 |
Correct |
68 ms |
568 KB |
Ok! 864 queries used. |
3 |
Correct |
62 ms |
512 KB |
Ok! 792 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
512 KB |
Ok! 1461 queries used. |
2 |
Correct |
246 ms |
512 KB |
Ok! 2142 queries used. |
3 |
Correct |
158 ms |
512 KB |
Ok! 1522 queries used. |
4 |
Correct |
185 ms |
512 KB |
Ok! 1668 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
177 ms |
512 KB |
Ok! 1606 queries used. |
2 |
Correct |
172 ms |
512 KB |
Ok! 1611 queries used. |
3 |
Correct |
216 ms |
512 KB |
Ok! 1842 queries used. |
4 |
Correct |
155 ms |
512 KB |
Ok! 1504 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
200 ms |
512 KB |
Too many queries! 1893 out of 1775 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
205 ms |
572 KB |
Too many queries! 1863 out of 1625 |
2 |
Halted |
0 ms |
0 KB |
- |