oj.uz

Submission #225954

# Submission time Handle Problem Language Result Execution time Memory
225954 2020-04-22T05:07:17 Z erd1 Park (JOI17_park) C++14
90 / 100
 279 ms 768 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;
    vector<int> pend;
    if(ask(x, p)) {
        answer(x, p);
        //cout << "found " << p << " " << x << endl;
        Place[x] = Place[p] = false;
        pend.pb(p);
    }else
    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;
        answer(pool[l], x);
        pend.pb(pool[l]);
        pool.erase(pool.begin()+l);
    }
    Place[x] = false;
    for(auto i: pend)for(auto ii: G[i])CheckEdge(x, ii, b);
}
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 == 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(T == 1)
            for(int it = find(all(ord), x)-ord.begin()+1; it < ord.size(); it++)
            for(auto j: vs)badcheck(ord[it], j);
        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:126:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
                                 ~^~
park.cpp:127:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             (ask(x, p)?r:l) = (l+r>>1);
                                ~^~
park.cpp:131: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:62: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int it = find(all(ord), x)-ord.begin()+1; it < ord.size(); it++)
                                                           ~~~^~~~~~~~~~~~
park.cpp:171: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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong Answer[3]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 672 KB Output is correct
2 Correct 164 ms 640 KB Output is correct
3 Correct 164 ms 572 KB Output is correct
4 Correct 168 ms 640 KB Output is correct
5 Correct 147 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 504 KB Output is correct
2 Correct 238 ms 760 KB Output is correct
3 Correct 235 ms 504 KB Output is correct
4 Correct 238 ms 768 KB Output is correct
5 Correct 225 ms 652 KB Output is correct
6 Correct 232 ms 504 KB Output is correct
7 Correct 231 ms 736 KB Output is correct
8 Correct 231 ms 504 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 512 KB Output is correct
2 Correct 215 ms 632 KB Output is correct
3 Correct 213 ms 512 KB Output is correct
4 Correct 177 ms 512 KB Output is correct
5 Correct 211 ms 512 KB Output is correct
6 Correct 170 ms 632 KB Output is correct
7 Correct 172 ms 512 KB Output is correct
8 Correct 206 ms 760 KB Output is correct
9 Correct 198 ms 508 KB Output is correct
10 Correct 207 ms 556 KB Output is correct
11 Correct 228 ms 632 KB Output is correct
12 Correct 223 ms 504 KB Output is correct
13 Correct 149 ms 512 KB Output is correct
14 Correct 228 ms 512 KB Output is correct
15 Correct 147 ms 512 KB Output is correct
16 Correct 234 ms 512 KB Output is correct
17 Correct 173 ms 632 KB Output is correct
18 Correct 217 ms 512 KB Output is correct
19 Correct 159 ms 640 KB Output is correct
20 Correct 198 ms 512 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 632 KB Output is correct
2 Correct 266 ms 512 KB Output is correct
3 Correct 247 ms 632 KB Output is correct
4 Correct 215 ms 760 KB Output is correct
5 Correct 275 ms 632 KB Output is correct
6 Correct 165 ms 760 KB Output is correct
7 Correct 269 ms 512 KB Output is correct
8 Correct 238 ms 512 KB Output is correct
9 Correct 242 ms 632 KB Output is correct
10 Correct 247 ms 552 KB Output is correct
11 Correct 213 ms 512 KB Output is correct
12 Correct 214 ms 512 KB Output is correct
13 Correct 206 ms 632 KB Output is correct
14 Correct 279 ms 512 KB Output is correct
15 Correct 220 ms 512 KB Output is correct
16 Correct 232 ms 632 KB Output is correct
17 Correct 170 ms 632 KB Output is correct
18 Correct 208 ms 576 KB Output is correct