| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127597 |
2019-07-09T16:00:23 Z |
Abelyan |
ICC (CEOI16_icc) |
C++17 |
|
149 ms |
760 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x);
#define dbgv(v);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
#define LOCAL
#include "icc.h"
/*
#ifdef LOCAL
int query(int n,int m,int a[],int b[]){
FOR(i,n)cout<<a[i]<<" ";
cout<<endl;
FOR(i,m)cout<<b[i]<<" ";
cout<<endl;
int ans;
cin>>ans;
return ans;
}
void setRoad(int a,int b){
cout<<"! "<<a<<" "<<b<<endl;
}
#endif
*/
const int N=1000;
vector<int> comps[N];
int a[N],b[N],asz,bsz;
int compham[N];
vector<int> tv[N];
int l,r;
void add(vector<int> v){
FOR(i,v.size()/2){
trav(j,comps[v[i]]){
a[asz++]=j;
}
}
FORT(i,v.size()/2,v.size()-1){
trav(j,comps[v[i]]){
b[bsz++]=j;
}
}
}
void split(vector<int> v){
r++;
FOR(i,v.size()/2){
tv[r].ad(v[i]);
}
r++;
FORT(i,v.size()/2,v.size()-1){
tv[r].ad(v[i]);
}
}
void adda(int k){
a[asz++]=k;
}
void addb(int k){
b[bsz++]=k;
}
void mrg(int ham1,int ham2){
//cout<<ham1<<" "<<ham2<<" "<<comps[ham1][0]<<" "<<comps[ham2][0]<<endl;
FOR(i,comps[ham2].size()){
comps[ham1].ad(comps[ham2][i]);
compham[comps[ham2][i]]=ham1;
//cout<<"hey "<<comps[ham2][i]<<endl;
}
comps[ham2].clear();
}
void run(int n){
//assert(0);
//srand(12433);
FORT(i,1,n){
comps[i].ad(i);
compham[i]=i;
}
//assert(0);
//assert(n<=1);
for (int qaylihamar=0;qaylihamar<n-1;qaylihamar++){
//assert(0);
//random_shuffle(comps+1,comps+1+n);
FORT(i,1,n){
if (comps[i].size())tv[0].ad(i);
}
l=r=0;
//assert(0);
while(true){
asz=bsz=0;
FORT(i,l,r){
add(tv[i]);
}
//cout<<1<<endl;
//assert(0);
if (query(asz,bsz,a,b)){
break;
}
//cout<<2<<endl;
int naxr=r;
FORT(i,l,naxr){
split(tv[i]);
}
//cout<<3<<endl;
l=naxr+1;
}
FOR(i,r+1)tv[i].clear();
vector<int> av,bv;
FOR(i,asz)av.ad(a[i]);
FOR(i,bsz)bv.ad(b[i]);
l=0;
r=bsz-1;
while(l!=r){
int md=(l+r)/2;
bsz=0;
FORT(i,l,md){
addb(bv[i]);
}
if (query(asz,bsz,a,b)){
r=md;
}
else{
l=md+1;
}
}
int gagat1=bv[l];
bsz=1;
b[0]=gagat1;
l=0;
r=asz-1;
while(l!=r){
int md=(l+r)/2;
asz=0;
FORT(i,l,md){
adda(av[i]);
}
if (query(asz,bsz,a,b)){
r=md;
}
else{
l=md+1;
}
}
int gagat2=av[l];
setRoad(gagat1,gagat2);
mrg(compham[gagat1],compham[gagat2]);
//cout<<"hello"<<endl;
}
}
/*
#ifdef LOCAL
int main(){
int n;
cin>>n;
run(n);
return 0;
}
#endif
*/
Compilation message
icc.cpp: In function 'void add(std::vector<int>)':
icc.cpp:10:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
icc.cpp:58:5: note: in expansion of macro 'FOR'
FOR(i,v.size()/2){
^~~
icc.cpp:12:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
^
icc.cpp:63:5: note: in expansion of macro 'FORT'
FORT(i,v.size()/2,v.size()-1){
^~~~
icc.cpp: In function 'void split(std::vector<int>)':
icc.cpp:10:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
icc.cpp:72:5: note: in expansion of macro 'FOR'
FOR(i,v.size()/2){
^~~
icc.cpp:12:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
^
icc.cpp:76:5: note: in expansion of macro 'FORT'
FORT(i,v.size()/2,v.size()-1){
^~~~
icc.cpp: In function 'void mrg(int, int)':
icc.cpp:10:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,a) for (int i=0;i<(a);++i)
^
icc.cpp:91:5: note: in expansion of macro 'FOR'
FOR(i,comps[ham2].size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
504 KB |
Ok! 106 queries used. |
| 2 |
Correct |
9 ms |
632 KB |
Ok! 102 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
504 KB |
Ok! 545 queries used. |
| 2 |
Correct |
45 ms |
504 KB |
Ok! 595 queries used. |
| 3 |
Correct |
45 ms |
632 KB |
Ok! 595 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
624 KB |
Ok! 1427 queries used. |
| 2 |
Correct |
136 ms |
624 KB |
Ok! 1472 queries used. |
| 3 |
Correct |
143 ms |
624 KB |
Ok! 1563 queries used. |
| 4 |
Correct |
137 ms |
632 KB |
Ok! 1487 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
628 KB |
Ok! 1499 queries used. |
| 2 |
Correct |
141 ms |
752 KB |
Ok! 1512 queries used. |
| 3 |
Correct |
142 ms |
620 KB |
Ok! 1520 queries used. |
| 4 |
Correct |
143 ms |
504 KB |
Ok! 1492 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
624 KB |
Ok! 1493 queries used. |
| 2 |
Correct |
138 ms |
632 KB |
Ok! 1475 queries used. |
| 3 |
Correct |
149 ms |
632 KB |
Ok! 1528 queries used. |
| 4 |
Correct |
145 ms |
760 KB |
Ok! 1552 queries used. |
| 5 |
Correct |
144 ms |
632 KB |
Ok! 1504 queries used. |
| 6 |
Correct |
147 ms |
632 KB |
Ok! 1553 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
732 KB |
Ok! 1523 queries used. |
| 2 |
Correct |
137 ms |
632 KB |
Ok! 1472 queries used. |
