Submission #225935

#	Time	Username	Problem	Language	Result	Execution time	Memory
225935		erd1	Park (JOI17_park)	C++14	67 / 100	187 ms	768 KiB

park

#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], 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;
    reverse(all(ans));
    return ans;
}
vector<vector<pii>> G;

void CheckEdge(int x, int p, vector<int>& pool){
    //cout << x << " " << p << pool << endl;
    for(auto [j, pos]: G[p]){
        for(auto i: pool)Place[i] = true; Place[p] = false; Place[x] = true;
        if(!ask(x, j))continue;
        //cout << "start finding!" << endl << j << " " << pos << endl;
        int l = pos, r = pool.size();
        for(auto i: pool)Place[i] = false; Place[x] = Place[j] = true;
        if(ask(x, j))answer(x, j);
        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]] = true; Place[p] = false;
                (ask(x, j)?r:l) = (l+r>>1);
            }
            if(l == pos)break; r--;
            //cout << "found edge" << pool[l] << " " << x << endl;
            answer(pool[l], x);
            l = pos;
        }
    }
    for(auto i: pool)Place[i] = 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 << vs << endl;
        for(auto j: vs)CheckEdge(j, x, ord);
        for(int j = 0, last = x; j < vs.size(); j++)G[last].pb({vs[j], ord.size()+j}), last = vs[j];
        //cout << G << endl;
        copy(all(vs), inserter(ord, ord.end()));
        ////cout << ord << endl;
        vs.resize(0);
    }
}

Compilation message (stderr)

park.cpp: In function 'int FindLink(int, int, std::vector<int>)':
park.cpp:67:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         for(int i = (l+r>>1); i < v.size();i++)Place[v[i]] = 0;
                      ~^~
park.cpp:67: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:68:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         (ask(v[0], x)?r:l) = l+r>>1;
                              ~^~
park.cpp:69: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:83:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = 1;
                                 ~^~
park.cpp:84:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             (ask(x, y)?r:l) = (l+r>>1);
                                ~^~
park.cpp: In function 'void CheckEdge(int, int, std::vector<int>&)':
park.cpp:100:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [j, pos]: G[p]){
              ^
park.cpp:101:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(auto i: pool)Place[i] = true; Place[p] = false; Place[x] = true;
         ^~~
park.cpp:101:43: 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[p] = false; Place[x] = true;
                                           ^~~~~
park.cpp:105:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(auto i: pool)Place[i] = false; Place[x] = Place[j] = true;
         ^~~
park.cpp:105:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
         for(auto i: pool)Place[i] = false; Place[x] = Place[j] = true;
                                            ^~~~~
park.cpp:110:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = true; Place[p] = false;
                                     ~^~
park.cpp:110:17: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
                 for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = true; Place[p] = false;
                 ^~~
park.cpp:110:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
                 for(int i = 0; i < (l+r>>1); i++)Place[pool[i]] = true; Place[p] = false;
                                                                         ^~~~~
park.cpp:111:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 (ask(x, j)?r:l) = (l+r>>1);
                                    ~^~
park.cpp:113:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(l == pos)break; r--;
             ^~
park.cpp:113:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
             if(l == pos)break; r--;
                                ^
park.cpp: In function 'void Detect(int, int)':
park.cpp:142: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], ord.size()+j}), last = vs[j];
                                  ~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23