oj.uz

답안 #225951

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225951 2020-04-22T04:56:59 Z erd1 Park (JOI17_park) C++14
67 / 100
 253 ms 760 KB 
#include "park.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
using namespace std;
typedef pair<int, int> pii;

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
    for(Iter i = b; i != e; i++)
        out << (i == b?"":" ") << *i;
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v){
    return outIt(out << '[', all(v)) << ']';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> v){
    return out << "(" << v.first << ", " << v.second << ")";
}


static int Place[1400];

int ran(int t = INT_MAX){
    static int x = 10292837;
    return ((x*0xdefaced+1)&INT_MAX)%t;
}

bool ask(int l, int r){
    //cout << l << " " << r << endl; for(int i = 0; i < 6; i++)cout << Place[i] << " "; cout << endl;
    return Ask(min(l, r), max(l, r), Place);
}

void answer(int l, int r){
    //cout << l << " a " << r << endl;
    Answer(min(l, r), max(l, r));
}

void Sort(int l, int r, vector<int>& v){
    ////cout << l << " " <<r << " " << v<< endl;
    if(v.size() == 0) return answer(l, r);
    if(v.size() == 1) return answer(l, v[0]), answer(v[0], r);
    int pivot = v[ran(v.size())];
    for(auto i: v)Place[i] = 1;
    Place[l] = Place[r] = 1;
    vector<int> R, L;
    for(auto i: v)
        if(i != pivot)
            Place[i] = 0, (ask(l, pivot)?R:L).pb(i), Place[i] = 1;
    for(auto i: v)Place[i] = 0;
    Place[l] = Place[r] = 0;
    Sort(l, pivot, L); Sort(pivot, r, R);
    auto st = copy(all(L), v.begin());
    *st = pivot;
    copy(all(R), next(st));
}
int FindLink(int N, int x, vector<int> v){
    int l = 0, r = v.size();
    ////cout << "FindLink" << v << endl;
    for(int i = 0; i < N; i++)Place[i] = 1;
    while(r-l > 1){
        for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0;
        (ask(v[0], x)?r:l) = l+r>>1;
        for(int i = 0; i < v.size();i++)Place[v[i]] = 1;
    }
    for(int i = 0; i < N; i++)Place[i] = 0;
    return v[l];
}
vector<int> Findchain(int x, int y, vector<int>& pool){
    ////cout << "Findchain" << endl;
    Place[x] = Place[y] = 1;
    vector<int> ans;
    if(ask(x, y))return Place[x] = Place[y] = 0, ans;
    int l = -1, r = pool.size();
    while(true){
        while(r-l > 1){
            for(auto i: pool)Place[i] = false;
            for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
            (ask(x, y)?r:l) = (l+r>>1);
        }
        if(r == 0)break;
        ans.pb(pool[r-1]); Place[pool[r-1]] = 1;
        pool.erase(pool.begin()+r-1);
        l = -1;
    }
    for(auto i: pool)Place[i] = false;
    for(auto i: ans)Place[i] = false;
    Place[x] = Place[y] = 0;
    reverse(all(ans));
    return ans;
}
vector<vector<int>> G;

void MakePool(int p, int x, vector<int>& v){
    v.pb(p);
    for(auto i: G[p])if(i != x)MakePool(i, x, v);
}

void CheckEdge(int x, int p, int b){
    //cout << pool << endl;
    vector<int> pool;
    MakePool(p, b, pool);
    //cout << "Check " << x << " " << p << " " << b << " " << pool << endl;
    for(auto i: pool)Place[i] = true; Place[x] = true;
    if(!ask(x, p)){
        for(auto i: pool)Place[i] = 0; Place[x] = 0;
        return;
    }
    //cout << "incheck" << endl;
    for(auto i: pool)Place[i] = 0;
    Place[x] = Place[p] = true;
    if(ask(x, p)) {
        answer(x, p);
        //cout << "found " << p << " " << x << endl;
        Place[x] = Place[p] = false;
        for(auto i: G[p])
            CheckEdge(x, i, b);
        return;
    }
    while(true){
        int l = 0, r = pool.size()+1;
        while(r-l > 1){
            for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
            (ask(x, p)?r:l) = (l+r>>1);
            for(auto i: pool)Place[i] = false;
        }
        //cout << l << " " << r << endl;
        if(l == pool.size())break;
        //cout << "found " << pool[l] << " " << x << endl;
        answer(pool[l], x);
        pool.erase(pool.begin()+l, pool.end());
    }
    Place[x] = false;
}
void badcheck(int i, int j){
    Place[i] = Place[j] = true;
    if(ask(i, j))answer(i, j);
    Place[i] = Place[j] = false;
}
vector<int> v, ord, pool;
vector<bool> used;
void Detect(int T, int N) {
    v.resize(N-1); G.resize(N);
    iota(all(v), 1);
    pool.resize(N-1); iota(all(pool), 1);
    used.resize(N);
    ord.pb(0);
    random_shuffle(all(v), ran);
    ////cout << v << endl;
    for(auto i: v){
        if(used[i])continue;
        int x = FindLink(N, i, ord); // maybe i -> (>x)
        pool.erase(find(all(pool), i));
        auto vs = Findchain(x, i, pool);
        //cout << x << " " << i << vs << endl;
        for(auto j: vs)used[j] = true;
        Sort(x, i, vs);
        vs.pb(i);
        //cout << x << " " << vs << endl;
        if(T == 1 || T == 5)
        //for(int it = find(all(ord), x)-ord.begin()+1; it < ord.size(); it++)
        for(auto j: vs)for(auto i: G[x])CheckEdge(j, i, x);
        if(x)for(auto j: vs)CheckEdge(j, 0, x);
        for(int j = 0, last = x; j < vs.size(); j++)G[last].pb(vs[j]), last = vs[j];
        //cout << G << endl;
        copy(all(vs), inserter(ord, ord.end()));
        //cout << ord << endl;
        vs.resize(0);
    }
}

Compilation message

park.cpp: In function 'int FindLink(int, int, std::vector<int>)':
park.cpp:66:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0;
                      ~^~
park.cpp:66:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0;
                               ~~^~~~~~~~~~
park.cpp:67:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         (ask(v[0], x)?r:l) = l+r>>1;
                              ~^~
park.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v.size();i++)Place[v[i]] = 1;
                        ~~^~~~~~~~~~
park.cpp: In function 'std::vector<int> Findchain(int, int, std::vector<int>&)':
park.cpp:82:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
                                 ~^~
park.cpp:83:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             (ask(x, y)?r:l) = (l+r>>1);
                                ~^~
park.cpp: In function 'void CheckEdge(int, int, int)':
park.cpp:108:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto i: pool)Place[i] = true; Place[x] = true;
     ^~~
park.cpp:108:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto i: pool)Place[i] = true; Place[x] = true;
                                       ^~~~~
park.cpp:110:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(auto i: pool)Place[i] = 0; Place[x] = 0;
         ^~~
park.cpp:110:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for(auto i: pool)Place[i] = 0; Place[x] = 0;
                                        ^~~~~
park.cpp:127:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
                                 ~^~
park.cpp:128:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             (ask(x, p)?r:l) = (l+r>>1);
                                ~^~
park.cpp:132:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(l == pool.size())break;
            ~~^~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:168:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0, last = x; j < vs.size(); j++)G[last].pb(vs[j]), last = vs[j];
                                  ~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 11 ms 384 KB Wrong Answer[6]
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 608 KB Output is correct
2 Correct 166 ms 632 KB Output is correct
3 Correct 161 ms 632 KB Output is correct
4 Correct 165 ms 632 KB Output is correct
5 Correct 147 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 632 KB Output is correct
2 Correct 237 ms 632 KB Output is correct
3 Correct 234 ms 508 KB Output is correct
4 Correct 236 ms 760 KB Output is correct
5 Correct 224 ms 512 KB Output is correct
6 Correct 235 ms 504 KB Output is correct
7 Correct 230 ms 512 KB Output is correct
8 Correct 228 ms 504 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 512 KB Output is correct
2 Correct 214 ms 504 KB Output is correct
3 Correct 209 ms 640 KB Output is correct
4 Correct 175 ms 512 KB Output is correct
5 Correct 207 ms 632 KB Output is correct
6 Correct 178 ms 512 KB Output is correct
7 Correct 175 ms 512 KB Output is correct
8 Correct 199 ms 512 KB Output is correct
9 Correct 195 ms 512 KB Output is correct
10 Correct 202 ms 512 KB Output is correct
11 Correct 225 ms 632 KB Output is correct
12 Correct 221 ms 512 KB Output is correct
13 Correct 144 ms 512 KB Output is correct
14 Correct 227 ms 512 KB Output is correct
15 Correct 145 ms 512 KB Output is correct
16 Correct 232 ms 520 KB Output is correct
17 Correct 169 ms 760 KB Output is correct
18 Correct 215 ms 512 KB Output is correct
19 Correct 157 ms 512 KB Output is correct
20 Correct 195 ms 552 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 253 ms 512 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -