답안 #35490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35490 2017-11-23T00:59:02 Z imaxblue CEOI16_icc (CEOI16_icc) C++14
100 / 100
153 ms 2224 KB
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

//void setRoad(int a, int b);
//int query(int x, int y, int a[], int b[]);
/*void setRoad(int x, int y){cout << "*" << x << ' ' << y << endl;}
bool query(int x, int y, vector<int> v, vector<int> w){
    fox(l, x) cout << v[l] << ' '; cout << endl;
    fox(l, y) cout << w[l] << ' '; cout << endl;
    int ans;
    cin >> ans;
    return ans;
};*/
int x, y, n, a[105], b[105];
vector<int> v, w, u;
vector<vector<int> > com;
vector<pair<int, vector<int> > > c2;
bool query2(int x, int y, vector<int> V, vector<int> W){
    vector<int> t1, t2;
    t1=t2=vector<int>();
    fox(l, x){
        fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
    }
    fox(l, y){
        fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
    }
    fox(l, t1.size()) a[l]=t1[l];
    fox(l, t2.size()) b[l]=t2[l];
    return query(t1.size(), t2.size(), a, b);
}
bool query3(int x, int y, vector<int> V, vector<int> W){
    fox(l, x) a[l]=V[l];
    fox(l, y) b[l]=W[l];
    return query(x, y, a, b);
}
void solve(){
    vector<int> t1, t2;
    t1=t2=vector<int>();
    fox(l, v.size()){
        fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
    }
    fox(l, w.size()){
        fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
    }
    v=t1; w=t2;
    int lo=0, mid, hi=v.size()-1;
    while(lo<hi){
        mid=(lo+hi)/2;
        u.clear();
        fox(l, mid+1) u.pb(v[l]);
        if (query3(mid+1, w.size(), u, w)){
            hi=mid;
        } else {
            lo=mid+1;
        }
    }
    x=v[lo];
    lo=0; hi=w.size()-1;
    while(lo<hi){
        mid=(lo+hi)/2;
        u.clear();
        fox(l, mid+1) u.pb(w[l]);
        if (query3(v.size(), mid+1, v, u)){
            hi=mid;
        } else {
            lo=mid+1;
        }
    }
    y=w[lo];
}
void get(){
    int b=64;
    while(b>=n) b/=2;
    for (; ; b>>=1){
        v.clear();
        w.clear();
        fox(l, n){
            if (b&l) v.pb(l);
            else w.pb(l);
        }
        //cout << b << endl;
        if (query2(v.size(), w.size(), v, w)){
            solve();
            //cout << b << endl;
            return;
        }
    }
}
int find_comp(int x){
        fox(l, com.size()){
            fox(l2, com[l].size()){
                if (com[l][l2]==x){
                    return l;
                }
            }
        }
}
void run(int N){
    n=N;
    fox1(l, n) com.pb(vector<int>(1, l));
    /*fox(l, N){
        v.pb(vector<int>(1, l+1));
    }*/
    fox(l, N-1){
        get();
        setRoad(x, y);
        x=find_comp(x);
        y=find_comp(y);
        fox(l, com[y].size()){
            com[x].pb(com[y][l]);
        }
        com.erase(com.begin()+y);
        c2.clear();
        fox(l, com.size()) c2.pb(mp(com[l].size(), com[l]));
        sort(c2.begin(), c2.end());
        fox(l, c2.size()){
            com[l]=c2[l].y;
        }
        --n;
        /*fox1(l, n){
            fox(l2, com[l].size()){
                cout<< com[l][l2] << ' ';
            }
            cout << endl;
        } cout << endl;*/
    }
}
/*int main(){
    run(4);
    return 0;
}*/

Compilation message

icc.cpp: In function 'bool query2(int, int, std::vector<int>, std::vector<int>)':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:46:9: note: in expansion of macro 'fox'
         fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
         ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:49:9: note: in expansion of macro 'fox'
         fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
         ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:51:5: note: in expansion of macro 'fox'
     fox(l, t1.size()) a[l]=t1[l];
     ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:52:5: note: in expansion of macro 'fox'
     fox(l, t2.size()) b[l]=t2[l];
     ^
icc.cpp: In function 'void solve()':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:63:5: note: in expansion of macro 'fox'
     fox(l, v.size()){
     ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:64:9: note: in expansion of macro 'fox'
         fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
         ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:66:5: note: in expansion of macro 'fox'
     fox(l, w.size()){
     ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:67:9: note: in expansion of macro 'fox'
         fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
         ^
icc.cpp: In function 'int find_comp(int)':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:114:9: note: in expansion of macro 'fox'
         fox(l, com.size()){
         ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:115:13: note: in expansion of macro 'fox'
             fox(l2, com[l].size()){
             ^
icc.cpp: In function 'void run(int)':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:133:9: note: in expansion of macro 'fox'
         fox(l, com[y].size()){
         ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:138:9: note: in expansion of macro 'fox'
         fox(l, com.size()) c2.pb(mp(com[l].size(), com[l]));
         ^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
icc.cpp:140:9: note: in expansion of macro 'fox'
         fox(l, c2.size()){
         ^
icc.cpp: In function 'int find_comp(int)':
icc.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 2084 KB Ok! 107 queries used.
2 Correct 6 ms 2088 KB Ok! 98 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2224 KB Ok! 557 queries used.
2 Correct 46 ms 2216 KB Ok! 639 queries used.
3 Correct 46 ms 2220 KB Ok! 626 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 2224 KB Ok! 1333 queries used.
2 Correct 146 ms 2216 KB Ok! 1570 queries used.
3 Correct 146 ms 2220 KB Ok! 1526 queries used.
4 Correct 153 ms 2224 KB Ok! 1514 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 2216 KB Ok! 1468 queries used.
2 Correct 136 ms 2220 KB Ok! 1512 queries used.
3 Correct 136 ms 2216 KB Ok! 1512 queries used.
4 Correct 126 ms 2220 KB Ok! 1373 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 2220 KB Ok! 1505 queries used.
2 Correct 143 ms 2220 KB Ok! 1502 queries used.
3 Correct 146 ms 2220 KB Ok! 1559 queries used.
4 Correct 143 ms 2220 KB Ok! 1527 queries used.
5 Correct 129 ms 2220 KB Ok! 1443 queries used.
6 Correct 143 ms 2220 KB Ok! 1602 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 2220 KB Ok! 1539 queries used.
2 Correct 139 ms 2220 KB Ok! 1496 queries used.