Submission #127597

#	Time	Username	Problem	Language	Result	Execution time	Memory
127597		Abelyan	ICC (CEOI16_icc)	C++17	100 / 100	149 ms	760 KiB

icc

#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 (stderr)

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()){
     ^~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10