제출 #606189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
606189		Theo830	ICC (CEOI16_icc)	C++17	100 / 100	264 ms	1064 KiB

icc

    #include <bits/stdc++.h>
    using namespace std;
    typedef int ll;
    const ll INF = 1e9+7;
    const ll MOD = 998244353;
    typedef pair<ll,ll> ii;
    #define iii pair<ll,ii>
    #define f(i,a,b) for(ll i = a;i < b;i++)
    #define pb push_back
    #define vll vector<ll>
    #define F first
    #define S second
    #define all(x) (x).begin(), (x).end()
    ///I hope I will get uprating and don't make mistakes
    ///I will never stop programming
    ///sqrt(-1) Love C++
    ///Please don't hack me
    ///@TheofanisOrfanou Theo830
    ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
    ///Stay Calm
    ///Look for special cases
    ///Beware of overflow and array bounds
    ///Think the problem backwards
    ///CEOI 2016 day 1
    #include "icc.h"
    /*
    int query(int size_a, int size_b, int a[], int b[]){
        cout<<size_a<<" : ";
        f(i,0,size_a){
            cout<<a[i]<<" ";
        }
        cout<<"\n";
        cout<<size_b<<" : ";
        f(i,0,size_b){
            cout<<b[i]<<" ";
        }
        cout<<"\n";
        ll v;
        cin>>v;
        return v;
    }
    */
    ll par[1005];
    ll find_par(ll a){
        if(par[a] == a){
            return a;
        }
        return par[a] = find_par(par[a]);
    }
    void enose(ll a,ll b){
        a = find_par(a);
        b = find_par(b);
        par[a] = b;
    }
    void run(int N){
        ll n = N;
        f(i,0,n+5){
            par[i] = i;
        }
        while(1){
            ll a = -1,b = -1;
            set<ll>com;
            vll exo[n+5];
            vll arr;
            f(i,1,n+1){
                exo[find_par(i)].pb(i);
                com.insert(find_par(i));
            }
            for(auto x:com){
                arr.pb(x);
            }
            vll AA,BB;
            set<ll>lathos[n+5];
            while(1){
                vll A[2];
                f(i,0,arr.size()){
                    A[i % 2].pb(arr[i]);
                }
                arr = A[0];
                for(auto x:A[1]){
                    arr.pb(x);
                }
                vll nA,nB;
                for(auto x:A[0]){
                    for(auto y:exo[x]){
                        nA.pb(y);
                    }
                }
                for(auto x:A[1]){
                    for(auto y:exo[x]){
                        nB.pb(y);
                    }
                }
                ll sa = nA.size();
                ll sb = nB.size();
                ll aa[sa],bb[sb];
                f(i,0,sa){
                    aa[i] = nA[i];
                }
                f(i,0,sb){
                    bb[i] = nB[i];
                }
                if(query(sa,sb,aa,bb) == 1){
                    AA = nA;
                    BB = nB;
                    break;
                }
                else{
                    for(auto x:A[0]){
                        for(auto y:A[1]){
                            lathos[x].insert(y);
                            lathos[y].insert(x);
                        }
                    }
                }
            }
            ll l = 0,r = AA.size() - 1;
            ll pos = r + 1;
            while(l <= r){
                ll mid = (l+r)/2;
                ll sa = AA.size();
                ll sb = BB.size();
                ll aa[mid+1],bb[sb];
                f(i,0,mid+1){
                    aa[i] = AA[i];
                }
                f(i,0,sb){
                    bb[i] = BB[i];
                }
                if(query(mid+1,sb,aa,bb) == 1){
                    r = mid - 1;
                    pos = min(pos,mid);
                }
                else{
                    l = mid + 1;
                }
            }
            a = AA[pos];
            vll C;
            for(auto x:BB){
                if(!lathos[find_par(a)].count(find_par(x))){
                    C.pb(x);
                }
            }
            BB = C;
            l = 0,r = BB.size() - 2;
            pos = r + 1;
            while(l <= r){
                ll mid = (l+r)/2;
                ll sa = AA.size();
                ll sb = BB.size();
                ll aa[sa],bb[mid+1];
                f(i,0,sa){
                    aa[i] = AA[i];
                }
                f(i,0,mid+1){
                    bb[i] = BB[i];
                }
                if(query(sa,mid+1,aa,bb) == 1){
                    r = mid - 1;
                    pos = min(pos,mid);
                }
                else{
                    l = mid + 1;
                }
            }
            b = BB[pos];
            setRoad(a,b);
            enose(a,b);
        }
    }
    /*
    int main(){
        run(4);
    }
    */

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'void run(int)':
icc.cpp:8:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     #define f(i,a,b) for(ll i = a;i < b;i++)
......
   76 |                 f(i,0,arr.size()){
      |                   ~~~~~~~~~~~~~~     
icc.cpp:76:17: note: in expansion of macro 'f'
   76 |                 f(i,0,arr.size()){
      |                 ^
icc.cpp:121:20: warning: unused variable 'sa' [-Wunused-variable]
  121 |                 ll sa = AA.size();
      |                    ^~
icc.cpp:151:20: warning: unused variable 'sb' [-Wunused-variable]
  151 |                 ll sb = BB.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