oj.uz

Submission #144998

# Submission time Handle Problem Language Result Execution time Memory
144998 2019-08-18T10:59:26 Z osaaateiasavtnl Library (JOI18_library) C++14
19 / 100
 760 ms 636 KB 
#include <bits/stdc++.h>
using namespace std; 
mt19937 rnd(228);
vector <int> ans, pos;
int N;
#ifdef HOME
int Q = 0;
int Query(vector <int> m) { 
    ++Q;
    vector <bool> used(N);
    for (int i = 0; i < N; ++i) {
        if (m[i]) used[pos[i]] = 1;
    }   
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += used[i] && (!i || !used[i - 1]);
    }   
    return ans;
}
void Answer(vector <int> a) { 
    //cout << "Q = " << Q << '\n';
    auto b = a; reverse(b.begin(), b.end());
    if (a == ans || b == ans) cout << "correct\n";
    else {
        for (int e : ans) cout << e << ' '; cout << '\n';
        for (int e : a) cout << e << ' '; cout << '\n';
        cout << "WA\n";
        exit(0);
    }
}
#else
#include "library.h"
#endif

#define ii pair <int, int>
#define app push_back
// Query()
// Answer()
vector <ii> ed;
vector <int> g[1001];
int query(vector<int> v) {
    vector<int> m(N,0);
    for(int i:v) m[i]=1;
    return Query(m);
}
int new_edge(vector <int> v) {
    int ans = v.size() - query(v);
    vector<int> m(N,0);
    for(int i:v) m[i]=1;    
    for (auto e : ed) ans -= m[e.first] && m[e.second];
    return ans; 
}
void Solve(int n) {
    N = n;
    for (int i = 0; i < 1001; ++i) g[i].clear();
    ed.clear();
    for (int t = 0; t < n - 1; ++t) {
        vector <int> cur;
        for (int i = 0; i < n; ++i) cur.app(i);
        while (cur.size() > 2) {
            int m = (cur.size() + 1) >> 1;
            while (1) {
                shuffle(cur.begin(), cur.end(), rnd);
                vector <int> tmp;
                for (int i = 0; i < m; ++i) tmp.app(cur[i]);
                if (new_edge(tmp)) {
                    cur = tmp;
                    break;
                }
            }   
        }
        ed.app({cur[0], cur[1]});
        g[cur[0]].app(cur[1]); g[cur[1]].app(cur[0]);
    }    
    vector <int> ans;
    for (int i = 0; i < n; ++i) {
        if (g[i].size() != 2) {
            ans.app(i); break;
        }
    }       
    int p = -1;
    for (int i = 0; i < n - 1; ++i) {
        for (int v : g[ans.back()]) {
            if (v != p) {
                p = ans.back();
                ans.app(v);
                break;
            }
        }
    }
    for (auto &e : ans) ++e;
    Answer(ans);
}
#ifdef HOME 
int main() {
    while (1) {
        int N = rnd() % 100 + 1;
        ans.clear();
        pos.resize(N);
        for (int i = 1; i <= N; ++i) ans.app(i);
        shuffle(ans.begin(), ans.end(), rnd);
        for (int i = 0; i < N; ++i) pos[ans[i] - 1] = i;
        Solve(N);
    }
}
#endif

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 348 KB # of queries: 3678
2 Correct 80 ms 376 KB # of queries: 3609
3 Correct 58 ms 348 KB # of queries: 3912
4 Correct 84 ms 252 KB # of queries: 3968
5 Correct 73 ms 348 KB # of queries: 3978
6 Correct 97 ms 404 KB # of queries: 4107
7 Correct 68 ms 356 KB # of queries: 3951
8 Correct 80 ms 348 KB # of queries: 3747
9 Correct 69 ms 352 KB # of queries: 4146
10 Correct 31 ms 348 KB # of queries: 2217
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 276 KB # of queries: 0
13 Correct 2 ms 504 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 5 ms 248 KB # of queries: 153
16 Correct 8 ms 376 KB # of queries: 286

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 348 KB # of queries: 3678
2 Correct 80 ms 376 KB # of queries: 3609
3 Correct 58 ms 348 KB # of queries: 3912
4 Correct 84 ms 252 KB # of queries: 3968
5 Correct 73 ms 348 KB # of queries: 3978
6 Correct 97 ms 404 KB # of queries: 4107
7 Correct 68 ms 356 KB # of queries: 3951
8 Correct 80 ms 348 KB # of queries: 3747
9 Correct 69 ms 352 KB # of queries: 4146
10 Correct 31 ms 348 KB # of queries: 2217
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 276 KB # of queries: 0
13 Correct 2 ms 504 KB # of queries: 3
14 Correct 2 ms 248 KB # of queries: 7
15 Correct 5 ms 248 KB # of queries: 153
16 Correct 8 ms 376 KB # of queries: 286
17 Incorrect 736 ms 512 KB Wrong Answer [3
18 Incorrect 725 ms 488 KB Wrong Answer [3
19 Incorrect 749 ms 636 KB Wrong Answer [3
20 Incorrect 705 ms 552 KB Wrong Answer [3
21 Incorrect 700 ms 352 KB Wrong Answer [3
22 Incorrect 760 ms 512 KB Wrong Answer [3
23 Incorrect 757 ms 392 KB Wrong Answer [3
24 Correct 311 ms 424 KB # of queries: 11266
25 Incorrect 719 ms 516 KB Wrong Answer [3
26 Incorrect 720 ms 424 KB Wrong Answer [3
27 Correct 326 ms 352 KB # of queries: 12403
28 Incorrect 720 ms 416 KB Wrong Answer [3
29 Incorrect 732 ms 380 KB Wrong Answer [3
30 Incorrect 734 ms 552 KB Wrong Answer [3