oj.uz

Submission #225955

# Submission time Handle Problem Language Result Execution time Memory
225955 2020-04-22T05:09:39 Z erd1 Park (JOI17_park) C++14
100 / 100
 281 ms 776 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) {
    if(T == 1){
        for(int i = 0; i < N && (Place[i] = 1); Place[i] = 0, i++)
            for(int j = i+1; j < N && (Place[j] = 1); Place[j] = 0, j++)
                if(Ask(i, j, Place))Answer(i, j);
        return;
    }
    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(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:174: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 13 ms 384 KB Output is correct
3 Correct 12 ms 384 KB Output is correct
4 Correct 12 ms 288 KB Output is correct
5 Correct 12 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 632 KB Output is correct
2 Correct 161 ms 548 KB Output is correct
3 Correct 163 ms 632 KB Output is correct
4 Correct 167 ms 632 KB Output is correct
5 Correct 146 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 512 KB Output is correct
2 Correct 235 ms 632 KB Output is correct
3 Correct 229 ms 632 KB Output is correct
4 Correct 233 ms 504 KB Output is correct
5 Correct 228 ms 760 KB Output is correct
6 Correct 236 ms 512 KB Output is correct
7 Correct 234 ms 504 KB Output is correct
8 Correct 234 ms 512 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 504 KB Output is correct
2 Correct 212 ms 528 KB Output is correct
3 Correct 210 ms 504 KB Output is correct
4 Correct 176 ms 512 KB Output is correct
5 Correct 205 ms 640 KB Output is correct
6 Correct 176 ms 512 KB Output is correct
7 Correct 172 ms 512 KB Output is correct
8 Correct 205 ms 512 KB Output is correct
9 Correct 192 ms 680 KB Output is correct
10 Correct 201 ms 512 KB Output is correct
11 Correct 228 ms 632 KB Output is correct
12 Correct 219 ms 512 KB Output is correct
13 Correct 149 ms 540 KB Output is correct
14 Correct 229 ms 632 KB Output is correct
15 Correct 145 ms 512 KB Output is correct
16 Correct 235 ms 632 KB Output is correct
17 Correct 170 ms 632 KB Output is correct
18 Correct 217 ms 512 KB Output is correct
19 Correct 160 ms 632 KB Output is correct
20 Correct 195 ms 512 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 512 KB Output is correct
2 Correct 274 ms 512 KB Output is correct
3 Correct 245 ms 632 KB Output is correct
4 Correct 215 ms 512 KB Output is correct
5 Correct 281 ms 512 KB Output is correct
6 Correct 170 ms 632 KB Output is correct
7 Correct 269 ms 512 KB Output is correct
8 Correct 244 ms 632 KB Output is correct
9 Correct 236 ms 512 KB Output is correct
10 Correct 243 ms 512 KB Output is correct
11 Correct 210 ms 512 KB Output is correct
12 Correct 211 ms 512 KB Output is correct
13 Correct 210 ms 776 KB Output is correct
14 Correct 278 ms 512 KB Output is correct
15 Correct 223 ms 512 KB Output is correct
16 Correct 237 ms 504 KB Output is correct
17 Correct 168 ms 632 KB Output is correct
18 Correct 206 ms 700 KB Output is correct