| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131193 |
2019-07-16T18:41:47 Z |
zubec |
ICC (CEOI16_icc) |
C++14 |
|
153 ms |
632 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int sz1, sz2, A[110], B[110];
int my_query(vector<int> &vec1, vector <int> &vec2){
sz1 = sz2 = 0;
for (int i = 0; i < vec1.size(); i++)
A[sz1++] = vec1[i];
for (int i = 0; i < vec2.size(); i++)
B[sz2++] = vec2[i];
return query(sz1, sz2, A, B);
}
int dsu[110];
int dsu_get(int v){
if (v == dsu[v])
return v;
return dsu[v] = dsu_get(dsu[v]);
}
void dsu_unite(int a, int b){
a = dsu_get(a);
b = dsu_get(b);
dsu[b] = a;
}
vector <int> g[110];
void run(int N){
n = N;
for (int i = 1; i <= n; i++){
dsu[i] = i;
}
for (int tt = 1; tt < n; tt++){
vector <int> vec;
for (int i = 1; i <= n; i++)
g[i].clear();
for (int i = 1; i <= n; i++){
vec.push_back(dsu_get(i));
g[dsu_get(i)].push_back(i);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
int mask = 0;
int lst = 0;
int sz = 0;
for (int bt = 0; ; bt++){
vector <int> vec1, vec2;
for (int j = 0; j < vec.size(); j++){
if (j & (1<<bt)){
for (int l = 0; l < g[vec[j]].size(); l++)
vec1.push_back(g[vec[j]][l]);
} else {
for (int l = 0; l < g[vec[j]].size(); l++)
vec2.push_back(g[vec[j]][l]);
}
}
if (vec1.empty() || vec2.empty())
break;
sz = bt;
if (my_query(vec1, vec2)){
mask |= (1<<bt);
lst = bt;
}
}
int mask1 = 0, mask2 = (1<<lst);
for (int bt = sz; bt >= 0; bt--){
if (bt == lst)
continue;
if (mask & (1<<bt)){
vector <int> vec1, vec2;
for (int j = 0; j < vec.size(); j++){
if ((j & (1<<bt)) && (j & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec1.push_back(g[vec[j]][l]);
} else
if (!(j & (1<<bt)) && !(j & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec2.push_back(g[vec[j]][l]);
}
}
if (vec1.empty() || vec2.empty() || !my_query(vec1, vec2))
mask1 |= (1<<bt); else
mask2 |= (1<<bt);
} else {
vector <int> vec1, vec2;
for (int j = 0; j < vec.size(); j++){
if (!(j & (1<<bt)) && (j & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec1.push_back(g[vec[j]][l]);
} else
if (!(j & (1<<bt)) && !(j & (1<<lst))){
for (int l = 0; l < g[vec[j]].size(); l++)
vec2.push_back(g[vec[j]][l]);
}
}
if (vec1.empty() || vec2.empty() || !my_query(vec1, vec2)){
mask1 |= (1<<bt);
mask2 |= (1<<bt);
}
}
}
vector <int> vec1 = g[vec[mask1]], vec2 = g[vec[mask2]];
int l = 0, r = vec1.size()-1;
while(l < r){
int mid = (l+r)>>1;
vector <int> cur;
for (int j = l; j <= mid; j++)
cur.push_back(vec1[j]);
if (my_query(cur, vec2))
r = mid; else
l = mid+1;
}
int a = vec1[l];
l = 0, r = vec2.size()-1;
while(l < r){
int mid = (l+r)>>1;
vector <int> cur;
for (int j = l; j <= mid; j++)
cur.push_back(vec2[j]);
if (my_query(vec1, cur))
r = mid; else
l = mid+1;
}
int b = vec2[l];
setRoad(a, b);
dsu_unite(a, b);
}
}
/**
4
2 4
1 3
1 4
*/
Compilation message
icc.cpp: In function 'int my_query(std::vector<int>&, std::vector<int>&)':
icc.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec1.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec2.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:55:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:57:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:60:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:78:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:80:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:84:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:93:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:95:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:99:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 116 queries used. |
| 2 |
Correct |
10 ms |
504 KB |
Ok! 116 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
504 KB |
Ok! 645 queries used. |
| 2 |
Correct |
42 ms |
504 KB |
Ok! 531 queries used. |
| 3 |
Correct |
45 ms |
632 KB |
Ok! 583 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
504 KB |
Ok! 1599 queries used. |
| 2 |
Correct |
131 ms |
504 KB |
Ok! 1287 queries used. |
| 3 |
Correct |
147 ms |
504 KB |
Ok! 1609 queries used. |
| 4 |
Correct |
149 ms |
508 KB |
Ok! 1583 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
504 KB |
Ok! 1566 queries used. |
| 2 |
Correct |
148 ms |
564 KB |
Ok! 1574 queries used. |
| 3 |
Correct |
145 ms |
600 KB |
Ok! 1587 queries used. |
| 4 |
Correct |
152 ms |
572 KB |
Ok! 1593 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
504 KB |
Ok! 1548 queries used. |
| 2 |
Correct |
142 ms |
560 KB |
Ok! 1556 queries used. |
| 3 |
Correct |
143 ms |
632 KB |
Ok! 1520 queries used. |
| 4 |
Correct |
145 ms |
564 KB |
Ok! 1587 queries used. |
| 5 |
Correct |
150 ms |
560 KB |
Ok! 1601 queries used. |
| 6 |
Correct |
153 ms |
560 KB |
Ok! 1602 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
600 KB |
Ok! 1587 queries used. |
| 2 |
Correct |
139 ms |
504 KB |
Ok! 1363 queries used. |
