oj.uz

Submission #145011

# Submission time Handle Problem Language Result Execution time Memory
145011 2019-08-18T11:56:09 Z osaaateiasavtnl Library (JOI18_library) C++14
19 / 100
 2000 ms 18064 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) { 
    if (m.size() == 1) return 1;
    ++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 add(int u, int v) {
    ed.app({u, v});
    g[u].app(v); g[v].app(u);
}
void rec(vector <int> a) {
    if (a.size() == 2) { add(a[0], a[1]); return; }   
    int m = a.size() >> 1;
    while (1) {     
        shuffle(a.begin(), a.end(), rnd);
        vector <int> l, r;
        for (int i = 0; i < m; ++i) l.app(a[i]);
        for (int i = m; i < a.size(); ++i) r.app(a[i]);
        bool t1 = new_edge(l), t2 = new_edge(r);
        if (!t1 && !t2) continue;
        if (t1) rec(l); if (t2) rec(r);
        break;
    }
}
void Solve(int n) {
    #ifdef HOME
    Q = 0;
    #endif
    N = n;
    for (int i = 0; i < 1001; ++i) g[i].clear();
    ed.clear();
    while (ed.size() < n - 1) {
        vector <int> cur;
        for (int i = 0; i < n; ++i) cur.app(i);
        rec(cur);        
    }
    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() {
    int t = 10;
    while (t--) {
        int N = 1000;
        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

Compilation message

library.cpp: In function 'void rec(std::vector<int>)':
library.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = m; i < a.size(); ++i) r.app(a[i]);
                         ~~^~~~~~~~~~
library.cpp:68:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if (t1) rec(l); if (t2) rec(r);
         ^~
library.cpp:68:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         if (t1) rec(l); if (t2) rec(r);
                         ^~
library.cpp: In function 'void Solve(int)':
library.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ed.size() < n - 1) {
            ~~~~~~~~~~^~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 248 KB # of queries: 3986
2 Correct 78 ms 432 KB # of queries: 3834
3 Correct 60 ms 348 KB # of queries: 4030
4 Correct 67 ms 376 KB # of queries: 4056
5 Correct 81 ms 248 KB # of queries: 4076
6 Correct 86 ms 248 KB # of queries: 3996
7 Correct 80 ms 248 KB # of queries: 4004
8 Correct 81 ms 380 KB # of queries: 3934
9 Correct 83 ms 432 KB # of queries: 4170
10 Correct 39 ms 424 KB # of queries: 2120
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 0
13 Correct 2 ms 248 KB # of queries: 8
14 Correct 2 ms 376 KB # of queries: 10
15 Correct 5 ms 248 KB # of queries: 164
16 Correct 7 ms 248 KB # of queries: 316

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 248 KB # of queries: 3986
2 Correct 78 ms 432 KB # of queries: 3834
3 Correct 60 ms 348 KB # of queries: 4030
4 Correct 67 ms 376 KB # of queries: 4056
5 Correct 81 ms 248 KB # of queries: 4076
6 Correct 86 ms 248 KB # of queries: 3996
7 Correct 80 ms 248 KB # of queries: 4004
8 Correct 81 ms 380 KB # of queries: 3934
9 Correct 83 ms 432 KB # of queries: 4170
10 Correct 39 ms 424 KB # of queries: 2120
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 248 KB # of queries: 0
13 Correct 2 ms 248 KB # of queries: 8
14 Correct 2 ms 376 KB # of queries: 10
15 Correct 5 ms 248 KB # of queries: 164
16 Correct 7 ms 248 KB # of queries: 316
17 Execution timed out 3037 ms 16000 KB Time limit exceeded
18 Execution timed out 3068 ms 16504 KB Time limit exceeded
19 Execution timed out 3058 ms 16044 KB Time limit exceeded
20 Execution timed out 3051 ms 17184 KB Time limit exceeded
21 Execution timed out 3021 ms 18064 KB Time limit exceeded
22 Execution timed out 3024 ms 16212 KB Time limit exceeded
23 Execution timed out 3087 ms 16424 KB Time limit exceeded
24 Correct 263 ms 376 KB # of queries: 10828
25 Execution timed out 3033 ms 16244 KB Time limit exceeded
26 Execution timed out 3079 ms 17720 KB Time limit exceeded
27 Correct 271 ms 376 KB # of queries: 10880
28 Execution timed out 3005 ms 16012 KB Time limit exceeded
29 Execution timed out 3100 ms 16812 KB Time limit exceeded
30 Execution timed out 3021 ms 16008 KB Time limit exceeded