| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 259222 |
2020-08-07T12:28:41 Z |
doowey |
ICC (CEOI16_icc) |
C++14 |
|
506 ms |
632 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
int ask(vector<int> ta, vector<int> tb){
int n = ta.size();
int m = tb.size();
int f1[n];
int f2[m];
for(int i = 0 ; i < n; i ++ )
f1[i]=ta[i];
for(int i = 0 ; i < m; i ++ )
f2[i]=tb[i];
return query(n, m, f1, f2);
}
const int MAXN = 105;
int par[MAXN];
int sz[MAXN];
int fin(int x){
if(x==par[x])
return x;
return par[x]=fin(par[x]);
}
void unite(int a, int b){
a=fin(a);
b=fin(b);
if(a==b)
return;
if(sz[a]>sz[b])swap(a,b);
par[a]=b;
sz[b]+=sz[a];
}
void run(int N){
for(int i = 1 ; i <= N ; i ++ )
par[i]=i,sz[i]=1;
int i1, i2;
for(int i = 0 ; i < N - 1; i ++ ){
vector<vector<int>> G(N + 1);
for(int j = 1; j <= N; j ++ ){
G[fin(j)].push_back(j);
}
vector<vector<int>> nw;
for(int j = 1; j <= N; j ++ ){
if(!G[j].empty())
nw.push_back(G[j]);
}
random_shuffle(nw.begin(), nw.end());
vector<pii>ord;
for(int i = 0 ; i + 1 < nw.size(); i ++ ){
ord.push_back(mp(max(i + 1, (int)nw.size() - i), i));
}
sort(ord.begin(), ord.end());
reverse(ord.begin(), ord.end());
int cut = -1;
for(auto p : ord){
vector<int> s1, s2;
for(int j = 0 ; j < nw.size(); j ++ ){
if(j <= p.se){
for(auto x : nw[j]) s1.push_back(x);
}
else{
for(auto x : nw[j]) s2.push_back(x);
}
}
if(ask(s1,s2)){
cut = p.se;
break;
}
}
vector<int> lis1, lis2;
for(int j = 0 ; j < nw.size(); j ++ ){
if(j <= cut) for(auto x : nw[j]) lis1.push_back(x);
else for(auto x : nw[j]) lis2.push_back(x);
}
int l = 0, r = lis1.size() - 1;
int mid;
while(l < r){
mid = (l + r ) / 2;
vector<int> fsh;
for(int j = 0 ; j <= mid; j ++){
fsh.push_back(lis1[j]);
}
if(ask(fsh,lis2))
r = mid;
else
l = mid + 1;
}
i1 = lis1[l];
l = 0, r = lis2.size() - 1;
while(l < r){
mid = (l + r) / 2;
vector<int> fsh;
for(int j = 0 ; j <= mid ; j ++ ){
fsh.push_back(lis2[j]);
}
if(ask(lis1,fsh)){
r = mid;
}
else{
l = mid + 1;
}
}
i2 = lis2[l];
setRoad(i1, i2);
unite(i1,i2);
}
}
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:60:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i + 1 < nw.size(); i ++ ){
~~~~~~^~~~~~~~~~~
icc.cpp:68:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < nw.size(); j ++ ){
~~^~~~~~~~~~~
icc.cpp:82:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < nw.size(); j ++ ){
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
512 KB |
Ok! 159 queries used. |
| 2 |
Correct |
9 ms |
512 KB |
Ok! 152 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
512 KB |
Ok! 1331 queries used. |
| 2 |
Correct |
124 ms |
512 KB |
Ok! 1631 queries used. |
| 3 |
Correct |
129 ms |
608 KB |
Ok! 1626 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
506 ms |
604 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
632 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
572 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
366 ms |
512 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
