| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127624 |
2019-07-09T17:28:16 Z |
Vardanyan |
ICC (CEOI16_icc) |
C++14 |
|
161 ms |
732 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> g[101];
int bt[101][100];
/*
int query(int n,int m,int* a,int* b){
cout<<n<<" "<<m<<endl;
for(int i = 0;i<n;i++) cout<<a[i]<<" ";
cout<<endl;
for(int i = 0;i<m;i++) cout<<b[i]<<" ";
cout<<endl;
int x;
cin>>x;
return x;
}*/
int a[101];
int b[101];
void run(int N){
int n = N;
for(int i = 1;i<=n;i++) g[i].push_back(i);
vector<int> v;
for(int i = 1;i<=n;i++) v.push_back(i);
int k = n-1;
while(k--){
for(int i = 0;i<v.size();i++){
for(int j = 0;j<20;j++){
bt[i][j] = (v[i]>>j)&1;
}
}
vector<int> f,s;
for(int i = 0;;i++){
f.clear();
s.clear();
for(int j = 0;j<v.size();j++){
if(bt[j][i]) f.push_back(v[j]);
else s.push_back(v[j]);
}
if(f.size() == 0 || s.size() == 0) continue;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int ps1 = 0;
int ps2 = 0;
for(int j = 0;j<f.size();j++){
// a[j] = f[j];
for(int jj = 0;jj<g[f[j]].size();jj++){
a[ps1++] = g[f[j]][jj];
}
}
for(int j = 0;j<s.size();j++){
// b[j] = s[j];
for(int jj = 0;jj<g[s[j]].size();jj++){
b[ps2++] = g[s[j]][jj];
}
}
int x;
x = query(ps1,ps2,a,b);
if(x) break;
}
int l = 0,r = f.size()-1;
int ans;
int ps1 = 0;
int ps2 = 0;
for(int j = 0;j<f.size();j++){
for(int jj = 0;jj<g[f[j]].size();jj++){
a[ps1++] = g[f[j]][jj];
}
}
for(int j = 0;j<s.size();j++){
for(int jj = 0;jj<g[s[j]].size();jj++){
b[ps2++] = g[s[j]][jj];
}
}
f.clear();
s.clear();
for(int j = 0;j<ps1;j++) f.push_back(a[j]);
for(int j = 0;j<ps2;j++) s.push_back(b[j]);
l = 0,r = f.size()-1;
// ans = 0;
for(int j = 0;j<s.size();j++) b[j] = s[j];
while(l<=r){
/*if(l == r){
break;
}*/
int mid = (l+r)/2;
memset(a,0,sizeof(a));
// memset(b,0,sizeof(b));
int ps = 0;
for(int j = l;j<=mid;j++){
a[ps] = f[j];
ps++;
}
int x;
x = query(mid-l+1,s.size(),a,b);
if(x){
ans = mid;
r = mid-1;
}
else l = mid+1;
}
l = 0,r = s.size()-1;
// ans2;
int ans2;
memset(a,0,sizeof(a));
for(int j = 0;j<f.size();j++) a[j] = f[j];
while(l<=r){
/* if(l == r){
break;
}*/
int mid = (l+r)/2;
memset(b,0,sizeof(b));
int ps = 0;
for(int j = l;j<=mid;j++){
b[ps] = s[j];
ps++;
}
int x;
x = query(f.size(),mid-l+1,a,b);
if(x){
ans2 = mid;
r = mid-1;
}
else l = mid+1;
}
ans = f[ans];
ans2 = s[ans2];
setRoad(ans,ans2);
// cout<<"found "<<ans<<" "<<ans2<<endl;
int comp1,comp2;
for(int j = 1;j<=n;j++){
for(int jj = 0;jj<g[j].size();jj++){
if(g[j][jj] == ans){
comp1 = j;
break;
}
}
}
for(int j = 1;j<=n;j++){
for(int jj = 0;jj<g[j].size();jj++){
if(g[j][jj] == ans2){
comp2 = j;
break;
}
}
}
for(int j = 0;j<g[comp2].size();j++){
g[comp1].push_back(g[comp2][j]);
}
g[comp2].clear();
v.clear();
for(int j = 1;j<=n;j++){
if(g[j].size()) v.push_back(j);
}
}
}
/*
int main() {
ios_base::sync_with_stdio(false);
run(4);
return 0;
}*/
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:26:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<v.size();i++){
~^~~~~~~~~
icc.cpp:35:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<v.size();j++){
~^~~~~~~~~
icc.cpp:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<f.size();j++){
~^~~~~~~~~
icc.cpp:46:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[f[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:50:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<s.size();j++){
~^~~~~~~~~
icc.cpp:52:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[s[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:64:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<f.size();j++){
~^~~~~~~~~
icc.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[f[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<s.size();j++){
~^~~~~~~~~
icc.cpp:70:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[s[j]].size();jj++){
~~^~~~~~~~~~~~~~~
icc.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<s.size();j++) b[j] = s[j];
~^~~~~~~~~
icc.cpp:106:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<f.size();j++) a[j] = f[j];
~^~~~~~~~~
icc.cpp:132:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[j].size();jj++){
~~^~~~~~~~~~~~
icc.cpp:140:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int jj = 0;jj<g[j].size();jj++){
~~^~~~~~~~~~~~
icc.cpp:147:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<g[comp2].size();j++){
~^~~~~~~~~~~~~~~~
icc.cpp:130:19: warning: 'comp2' may be used uninitialized in this function [-Wmaybe-uninitialized]
int comp1,comp2;
^~~~~
icc.cpp:127:22: warning: 'ans2' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans2 = s[ans2];
^
icc.cpp:126:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
ans = f[ans];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 111 queries used. |
| 2 |
Correct |
9 ms |
504 KB |
Ok! 108 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
504 KB |
Ok! 556 queries used. |
| 2 |
Correct |
50 ms |
504 KB |
Ok! 686 queries used. |
| 3 |
Correct |
50 ms |
504 KB |
Ok! 684 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
604 KB |
Ok! 1381 queries used. |
| 2 |
Correct |
161 ms |
600 KB |
Ok! 1691 queries used. |
| 3 |
Correct |
125 ms |
504 KB |
Ok! 1387 queries used. |
| 4 |
Correct |
143 ms |
632 KB |
Ok! 1522 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
504 KB |
Ok! 1441 queries used. |
| 2 |
Correct |
139 ms |
640 KB |
Ok! 1485 queries used. |
| 3 |
Correct |
156 ms |
732 KB |
Ok! 1653 queries used. |
| 4 |
Correct |
131 ms |
732 KB |
Ok! 1418 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
600 KB |
Ok! 1654 queries used. |
| 2 |
Correct |
154 ms |
632 KB |
Ok! 1633 queries used. |
| 3 |
Correct |
158 ms |
632 KB |
Ok! 1664 queries used. |
| 4 |
Correct |
150 ms |
636 KB |
Ok! 1607 queries used. |
| 5 |
Correct |
133 ms |
632 KB |
Ok! 1456 queries used. |
| 6 |
Correct |
148 ms |
604 KB |
Ok! 1559 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
504 KB |
Too many queries! 1641 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
