oj.uz

답안 #225934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225934 2020-04-22T03:52:19 Z erd1 Park (JOI17_park) C++14
67 / 100
 217 ms 796 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], 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(r == pos+1)break;
            //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) {
    if(T == 2){
        v.resize(N-2);
        iota(all(v), 1);
        Sort(0, N-1, v);
    }
    if(T == 3 || T == 4 || T == 5){
        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

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: In function 'void Detect(int, int)':
park.cpp:148:40: 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.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 512 KB Output is correct
2 Correct 44 ms 512 KB Output is correct
3 Correct 60 ms 512 KB Output is correct
4 Correct 70 ms 512 KB Output is correct
5 Correct 67 ms 640 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 504 KB Output is correct
2 Correct 212 ms 504 KB Output is correct
3 Correct 212 ms 760 KB Output is correct
4 Correct 208 ms 512 KB Output is correct
5 Correct 200 ms 512 KB Output is correct
6 Correct 208 ms 512 KB Output is correct
7 Correct 217 ms 640 KB Output is correct
8 Correct 208 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 384 KB Output is correct
2 Correct 189 ms 632 KB Output is correct
3 Correct 189 ms 560 KB Output is correct
4 Correct 155 ms 512 KB Output is correct
5 Correct 186 ms 512 KB Output is correct
6 Correct 171 ms 796 KB Output is correct
7 Correct 153 ms 512 KB Output is correct
8 Correct 179 ms 504 KB Output is correct
9 Correct 173 ms 504 KB Output is correct
10 Correct 182 ms 512 KB Output is correct
11 Correct 211 ms 512 KB Output is correct
12 Correct 200 ms 512 KB Output is correct
13 Correct 128 ms 512 KB Output is correct
14 Correct 210 ms 536 KB Output is correct
15 Correct 120 ms 508 KB Output is correct
16 Correct 212 ms 632 KB Output is correct
17 Correct 158 ms 512 KB Output is correct
18 Correct 202 ms 512 KB Output is correct
19 Correct 142 ms 512 KB Output is correct
20 Correct 178 ms 632 KB Output is correct

Subtask #5
0 / 23.0

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