| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30687 |
2017-07-26T06:20:56 Z |
zscoder |
ICC (CEOI16_icc) |
C++14 |
|
166 ms |
2096 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "icc.h"
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
static int par[111];
static vi ilab[111];
static int lab[111];
static void init(int N)
{
for(int i = 0; i < N; i++)
{
par[i]=i;
}
}
static int rt(int u)
{
if(par[u]==u) return u;
else
{
assert(par[u]<=u);
return (par[u]=rt(par[u]));
}
}
static void merge(int u, int v)
{
u=rt(u); v=rt(v);
if(u==v) return ;
if(u>v) swap(u,v);
par[v]=u;
}
int relabel(int N)
{
bool used[111];
memset(used,0,sizeof(used));
int cnt=0;
for(int i = 0; i < N; i++)
{
//cerr<<i<<' '<<par[i]<<'\n';
par[i]=rt(i);
ilab[i].clear();
if(!used[par[i]])
{
assert(par[i]==i);
lab[par[i]]=cnt;
ilab[cnt].pb(i);
cnt++;
used[par[i]]=1;
}
else
{
lab[i]=lab[par[i]];
ilab[lab[i]].pb(i);
}
}
return cnt;
}
static bool ask(vi &l, vi &r)
{
if(l.empty()||r.empty()) return 0;
int L[l.size()]; int R[r.size()];
for(int i=0;i<l.size();i++)
{
L[i]=l[i]+1;
//cerr<<l[i]<<' ';
}
//cerr<<'\n';
for(int i=0;i<r.size();i++)
{
R[i]=r[i]+1;
//cerr<<r[i]<<' ';
}
//cerr<<'\n';
bool tmp = query(l.size(),r.size(),L,R);
//cerr<<"RES : "<<tmp<<'\n';
return tmp;
}
void run(int N)
{
init(N);
for(int i = 0; i < N - 1; i++)
{
int mx = relabel(N);
int z = 0;
while((1<<z)<mx)
{
z++;
}
int xr = 0;
for(int i = 0; i < z; i++)
{
vi l,r;
for(int j = 0; j < mx; j++)
{
if(j&(1<<i))
{
for(int k = 0; k < ilab[j].size(); k++)
{
l.pb(ilab[j][k]);
}
}
else
{
for(int k = 0; k < ilab[j].size(); k++)
{
r.pb(ilab[j][k]);
}
}
}
if(ask(l,r))
{
xr^=(1<<i);
}
}
int a = 0;
int b = 0;
int s = 0;
for(int i=0;i<z;i++)
{
if((xr&(1<<i)))
{
s=i;
break;
}
}
a=(1<<s);
int mask = (1<<s);
for(int i = 0; i < z; i++)
{
if(i!=s)
{
vi L,R;
for(int j = 0; j < mx; j++)
{
if((j&mask)==a&&(j&(1<<i)))
{
for(int k=0;k<ilab[j].size();k++)
{
L.pb(ilab[j][k]);
}
}
}
for(int j = 0; j < mx; j++)
{
if((j&mask)==b)
{
if(xr&(1<<i))
{
if(!(j&(1<<i)))
{
for(int k=0;k<ilab[j].size();k++)
{
R.pb(ilab[j][k]);
}
}
}
else
{
if((j&(1<<i)))
{
for(int k=0;k<ilab[j].size();k++)
{
R.pb(ilab[j][k]);
}
}
}
}
}
if(ask(L,R))
{
a^=(1<<i);
if(!(xr&(1<<i))) b^=(1<<i);
}
else
{
if((xr&(1<<i))) b^=(1<<i);
}
mask^=(1<<i);
}
}
//CC a and CC b are connected
vi le,ri;
for(int i=0;i<N;i++)
{
if(lab[par[i]]==a) le.pb(i);
if(lab[par[i]]==b) ri.pb(i);
}
/*
cerr<<"L : ";
for(int i=0;i<le.size();i++) cerr<<le[i]<<' ';
cerr<<'\n';
cerr<<"R : ";
for(int i=0;i<ri.size();i++) cerr<<ri[i]<<' ';
cerr<<'\n';
*/
int u,v;
int lo = 0; int hi = int(le.size()) - 1;
int ans = -1;
while(lo<=hi)
{
if(ans!=-1) break;
int mid = (lo+hi)>>1;
if(lo==hi&&ans==-1)
{
ans=lo;
break;
}
vi L,R;
for(int i = lo; i <= mid; i++)
{
L.pb(le[i]);
}
for(int i = 0; i < ri.size(); i++)
{
R.pb(ri[i]);
}
if(ask(L,R))
{
if(mid==lo)
{
ans=mid;
}
hi = mid;
}
else
{
lo = mid + 1;
}
}
u = ans;
lo = 0; hi = int(ri.size()) - 1;
ans = -1;
while(lo<=hi)
{
if(ans!=-1) break;
int mid = (lo+hi)>>1;
if(lo==hi&&ans==-1)
{
ans=lo;
break;
}
vi L,R;
for(int i = 0; i < le.size(); i++)
{
L.pb(le[i]);
}
for(int i = lo; i <= mid; i++)
{
R.pb(ri[i]);
}
if(ask(L,R))
{
if(mid==lo)
{
ans=mid;
}
hi = mid;
}
else
{
lo = mid + 1;
}
}
v=ans;
//cerr<<"ANS : "<<le[u]<<' '<<ri[v]<<'\n';
setRoad(le[u]+1,1+ri[v]);
merge(le[u],ri[v]);
}
}
Compilation message
icc.cpp: In function 'bool ask(vi&, vi&)':
icc.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<l.size();i++)
^
icc.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<r.size();i++)
^
icc.cpp: In function 'void run(int)':
icc.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < ilab[j].size(); k++)
^
icc.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < ilab[j].size(); k++)
^
icc.cpp:163:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<ilab[j].size();k++)
^
icc.cpp:177:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<ilab[j].size();k++)
^
icc.cpp:187:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<ilab[j].size();k++)
^
icc.cpp:239:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ri.size(); i++)
^
icc.cpp:269:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < le.size(); i++)
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2088 KB |
Ok! 114 queries used. |
| 2 |
Correct |
6 ms |
2092 KB |
Ok! 107 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
2088 KB |
Ok! 619 queries used. |
| 2 |
Correct |
43 ms |
2092 KB |
Ok! 558 queries used. |
| 3 |
Correct |
43 ms |
2092 KB |
Ok! 570 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
2092 KB |
Ok! 1575 queries used. |
| 2 |
Correct |
139 ms |
2092 KB |
Ok! 1436 queries used. |
| 3 |
Correct |
133 ms |
2092 KB |
Ok! 1527 queries used. |
| 4 |
Correct |
139 ms |
2092 KB |
Ok! 1528 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
2088 KB |
Ok! 1489 queries used. |
| 2 |
Correct |
119 ms |
2088 KB |
Ok! 1493 queries used. |
| 3 |
Correct |
136 ms |
2088 KB |
Ok! 1467 queries used. |
| 4 |
Correct |
156 ms |
2088 KB |
Ok! 1537 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
2096 KB |
Ok! 1439 queries used. |
| 2 |
Correct |
149 ms |
2092 KB |
Ok! 1441 queries used. |
| 3 |
Correct |
133 ms |
2088 KB |
Ok! 1480 queries used. |
| 4 |
Correct |
153 ms |
2088 KB |
Ok! 1500 queries used. |
| 5 |
Correct |
139 ms |
2088 KB |
Ok! 1561 queries used. |
| 6 |
Correct |
149 ms |
2092 KB |
Ok! 1539 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
2088 KB |
Ok! 1472 queries used. |
| 2 |
Correct |
136 ms |
2092 KB |
Ok! 1436 queries used. |
