oj.uz

Submission #116479

# Submission time Handle Problem Language Result Execution time Memory
116479 2019-06-12T14:28:22 Z JohnTitor ICC (CEOI16_icc) C++11
100 / 100
 138 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "ICC"
#ifndef Aria
#include "icc.h"
#else
    int query(int as, int bs, int a[], int b[]){

    }

#endif // Aria
int r[201];
vector <int> g[201];
int root(int u){
    if(r[u]<0) return u;
    return r[u]=root(r[u]);
}
void unite(int u, int v){
    u=root(u);
    v=root(v);
    if(u==v) return;
    if(r[u]>r[v]) swap(u, v);
    for(int x: g[v]) g[u].pb(x);
    r[u]+=r[v];
    r[v]=u;
}
int cnt=0;
int a[200];
int b[200];
bool ask(vector <int> left, vector <int> right){
    cnt++;
    if(left.empty()||right.empty()){
        while(true){
            int c;
            writeln(c);
        }
    }
    FFOR(i, 0, left.size()) a[i]=left[i];
    FFOR(i, 0, right.size()) b[i]=right[i];
    return query(left.size(), right.size(), a, b);
}
bool askcomp(vector <int> left, vector <int> right){
    vector <int> rl;
    vector <int> rr;
    for(int x: left) for(int y: g[x]) rl.pb(y);
    for(int x: right) for(int y: g[x]) rr.pb(y);
    return ask(rl, rr);
}
void run(int n){
    FOR(i, 1, n){
        r[i]=-1;
        g[i].pb(i);
    }
    FFOR(cnt, 1, n){
        vector <int> component;
        FOR(i, 1, n) if(i==root(i)) component.pb(i);
        vector <int> left, right;
        FFOR(b, 0, 10){
            left.clear();
            right.clear();
            FFOR(i, 0, component.size()) if(bit(i, b)) left.pb(component[i]); else right.pb(component[i]);
            if(left.empty()||right.empty()) continue;
            if(b==__lg(component.size()-1)) break;
            if(askcomp(left, right)) break;
        }
        vector <int> tl, tr;
        tl=left;
        tr=right;
        left.clear();
        right.clear();
        for(int x: tl) for(int y: g[x]) left.pb(y);
        for(int x: tr) for(int y: g[x]) right.pb(y);
        while(left.size()>1){
            tl.clear();
            FFOR(i, 0, left.size()/2) tl.pb(left[i]);
            if(ask(tl, right)) left=tl;
            else{
                tl.clear();
                FFOR(i, left.size()/2, left.size()) tl.pb(left[i]);
                left=tl;
            }
        }
        while(right.size()>1){
            tr.clear();
            FFOR(i, 0, right.size()/2) tr.pb(right[i]);
            if(ask(left, tr)) right=tr;
            else{
                tr.clear();
                FFOR(i, right.size()/2, right.size()) tr.pb(right[i]);
                right=tr;
            }
        }
        if(left.empty()||right.empty()) ask(left, right);
        unite(left[0], right[0]);
        setRoad(left[0], right[0]);
    }
}

Compilation message

icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>)':
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:54:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, left.size()) a[i]=left[i];
     ^~~~
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:55:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, right.size()) b[i]=right[i];
     ^~~~
icc.cpp: In function 'void run(int)':
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:77:13: note: in expansion of macro 'FFOR'
             FFOR(i, 0, component.size()) if(bit(i, b)) left.pb(component[i]); else right.pb(component[i]);
             ^~~~
icc.cpp:79:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(b==__lg(component.size()-1)) break;
                ~^~~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:91:13: note: in expansion of macro 'FFOR'
             FFOR(i, 0, left.size()/2) tl.pb(left[i]);
             ^~~~
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:95:17: note: in expansion of macro 'FFOR'
                 FFOR(i, left.size()/2, left.size()) tl.pb(left[i]);
                 ^~~~
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:101:13: note: in expansion of macro 'FFOR'
             FFOR(i, 0, right.size()/2) tr.pb(right[i]);
             ^~~~
icc.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
icc.cpp:105:17: note: in expansion of macro 'FFOR'
                 FFOR(i, right.size()/2, right.size()) tr.pb(right[i]);
                 ^~~~
icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>)':
icc.cpp:50:17: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
             int c;
                 ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Ok! 93 queries used.
2 Correct 8 ms 512 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 512 KB Ok! 527 queries used.
2 Correct 45 ms 512 KB Ok! 649 queries used.
3 Correct 44 ms 512 KB Ok! 652 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 604 KB Ok! 1495 queries used.
2 Correct 133 ms 568 KB Ok! 1605 queries used.
3 Correct 136 ms 512 KB Ok! 1603 queries used.
4 Correct 138 ms 632 KB Ok! 1545 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 568 KB Ok! 1569 queries used.
2 Correct 136 ms 512 KB Ok! 1565 queries used.
3 Correct 127 ms 512 KB Ok! 1605 queries used.
4 Correct 133 ms 512 KB Ok! 1537 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 568 KB Ok! 1605 queries used.
2 Correct 129 ms 588 KB Ok! 1605 queries used.
3 Correct 128 ms 608 KB Ok! 1604 queries used.
4 Correct 126 ms 604 KB Ok! 1602 queries used.
5 Correct 131 ms 512 KB Ok! 1517 queries used.
6 Correct 135 ms 512 KB Ok! 1574 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 512 KB Ok! 1605 queries used.
2 Correct 129 ms 600 KB Ok! 1605 queries used.