oj.uz

Submission #116473

# Submission time Handle Problem Language Result Execution time Memory
116473 2019-06-12T14:20:53 Z JohnTitor ICC (CEOI16_icc) C++11
18 / 100
 49 ms 896 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[101];
vector <int> g[101];
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;
bool ask(vector <int> left, vector <int> right){
    cnt++;
    if(cnt>1700){
        while(true){
            int c;
            writeln(c);
        }
    }
    int a[100];
    int b[100];
    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(askcomp(left, right)) break;
        }
        vector <int> tl, tr;
        tl=left;
        tr=right;
        left.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;
            }
        }
        unite(left[0], right[0]);
        setRoad(left[0], right[0]);
    }
}
//int main(){
//    #ifdef Aria
//        if(fopen(taskname".in", "r"))
//            freopen(taskname".in", "r", stdin);
//    #endif // Aria
//}

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: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:89: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:93: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:99: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:103: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:48: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 7 ms 512 KB Ok! 103 queries used.
2 Correct 8 ms 456 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 512 KB Ok! 555 queries used.
2 Correct 49 ms 632 KB Ok! 737 queries used.
3 Correct 49 ms 512 KB Ok! 751 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -