| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131191 |
2019-07-16T18:37:31 Z |
zubec |
ICC (CEOI16_icc) |
C++14 |
|
161 ms |
632 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
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());
while(1){
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;
/*cout << "kek " << bt << endl;
for (int j = 0; j < vec1.size(); j++)
cout << vec1[j] << ' ';
cout << endl;
for (int j = 0; j < vec2.size(); j++)
cout << vec2[j] << ' ';
cout << endl;*/
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]];
/*cout << mask1 << ' ' << mask2 << ' ' << mask << endl;
cout << "kek " << vec1.size() << ' ' << vec2.size() << endl;
for (int j = 0; j < vec1.size(); j++)
cout << vec1[j] << ' ';
cout << endl;
for (int j = 0; j < vec2.size(); j++)
cout << vec2[j] << ' ';
cout << endl;*/
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();
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);
break;
}
}
}
/**
4
2 4
1 3
1 4
*/
Compilation message
icc.cpp: In function 'int my_query(std::vector<int>&, std::vector<int>&)':
icc.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec1.size(); i++)
~~^~~~~~~~~~~~~
icc.cpp:16: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:58:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:60:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:63:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:88:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:90:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:94:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:103:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++){
~~^~~~~~~~~~~~
icc.cpp:105:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int l = 0; l < g[vec[j]].size(); l++)
~~^~~~~~~~~~~~~~~~~~
icc.cpp:109:47: 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 |
10 ms |
504 KB |
Ok! 126 queries used. |
| 2 |
Correct |
10 ms |
504 KB |
Ok! 126 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
504 KB |
Ok! 693 queries used. |
| 2 |
Correct |
44 ms |
504 KB |
Ok! 563 queries used. |
| 3 |
Correct |
46 ms |
504 KB |
Ok! 604 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
568 KB |
Ok! 1695 queries used. |
| 2 |
Correct |
139 ms |
608 KB |
Ok! 1383 queries used. |
| 3 |
Correct |
154 ms |
572 KB |
Ok! 1703 queries used. |
| 4 |
Correct |
158 ms |
612 KB |
Ok! 1669 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
504 KB |
Ok! 1650 queries used. |
| 2 |
Correct |
155 ms |
632 KB |
Ok! 1641 queries used. |
| 3 |
Correct |
152 ms |
504 KB |
Ok! 1681 queries used. |
| 4 |
Correct |
161 ms |
572 KB |
Ok! 1687 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
504 KB |
Ok! 1664 queries used. |
| 2 |
Correct |
150 ms |
604 KB |
Ok! 1652 queries used. |
| 3 |
Correct |
150 ms |
504 KB |
Ok! 1612 queries used. |
| 4 |
Correct |
152 ms |
632 KB |
Ok! 1682 queries used. |
| 5 |
Correct |
157 ms |
504 KB |
Ok! 1693 queries used. |
| 6 |
Correct |
160 ms |
632 KB |
Ok! 1696 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
632 KB |
Too many queries! 1682 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
