oj.uz

Submission #768661

# Submission time Handle Problem Language Result Execution time Memory
768661 2023-06-28T10:43:42 Z raysh07 Library (JOI18_library) C++17
100 / 100
 275 ms 2820 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
vector<vector<int>> adj;
vector<int> comp;
vector<bool> vis;
vector<int> m;
vector<int> deg;
int q = 0;
 
void init(int n){
    for (int i = 0; i < n; i++) m[i] = 0;
}
 
int go(vector <int> m){
    q++;
    if (q > 20000) exit(0);
    
    return Query(m);
}
 
bool check(int i, int j, int n){
    if (i == j) return false;
    
    for (int k = i; k <= j; k++){
        m[k] = 1;
    }
    int cnt = 0;
    
    for (auto x : adj[i]) m[x] = 0;
    
    for (int i = 0; i < n; i++) cnt += m[i];
    
    if (cnt == 1) {
        init(n);
        return false;
    }
    
    int a1 = go(m);
    m[i] = 0;
    int a2;
    if (cnt != 2)
    a2 = go(m);
    else a2 = 1;
    
    init(n);
    return a2 >= a1;
}
 
void dfs(int u, int par = -1){
    comp.push_back(u + 1);
    vis[u] = true;
    for (int v : adj[u]){
        if (v != par){
            assert(!vis[v]);
            dfs(v, u);
        }
    }
}
 
void Solve(int n)
{
    if (n == 1){
        Answer({1});
        return;
    }
    if (n == 2){
        Answer({1, 2});
        return;
    }
    
    m.resize(n, 0);
    deg.resize(n, 0);
    adj.resize(1e5 + 69);
    vis.resize(1e5 + 69, false);
    
    vector <int> m(n, 1);
    vector <int> ok;
    ok.push_back(1);
    for (int i = 0; i < n; i++){
        m[i] = 0;
        if (i == n - 1){
            ok.push_back(0);
        } else if (i == n - 2){
            ok.push_back(1);
        } else {
            ok.push_back(Query(m));
        }
    }
    
    for (int i = 0; i < n; i++){
        deg[i] = ok[i + 1] - ok[i] + 1;
    }
 
    for (int i = 0; i < n; i++){
        int tm = 0;
        while (tm < deg[i]){
            int l = i + 1, r = n - 1;
            
            while (l != r){
                int m = (l + r)/2;
                
                if (check(i, m, n)) r = m;
                else l = m + 1;
            }
            
            adj[i].push_back(l);
            adj[l].push_back(i);
            tm++;
        }
    }
    
    for (int i = 0; i < n; i++){
        if (adj[i].size() == 1){
            dfs(i);
            break;
        }
    }
    assert(comp.size() == n);
    
    Answer(comp);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from library.cpp:1:
library.cpp: In function 'void Solve(int)':
library.cpp:119:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |     assert(comp.size() == n);
      |            ~~~~~~~~~~~~^~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2640 KB # of queries: 2824
2 Correct 34 ms 2692 KB # of queries: 2802
3 Correct 34 ms 2640 KB # of queries: 2978
4 Correct 37 ms 2676 KB # of queries: 2955
5 Correct 33 ms 2680 KB # of queries: 2966
6 Correct 33 ms 2664 KB # of queries: 2982
7 Correct 35 ms 2680 KB # of queries: 2974
8 Correct 23 ms 2680 KB # of queries: 2834
9 Correct 33 ms 2676 KB # of queries: 2937
10 Correct 21 ms 2676 KB # of queries: 1741
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 1 ms 2640 KB # of queries: 2
14 Correct 1 ms 2588 KB # of queries: 6
15 Correct 2 ms 2640 KB # of queries: 98
16 Correct 4 ms 2676 KB # of queries: 236

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2640 KB # of queries: 2824
2 Correct 34 ms 2692 KB # of queries: 2802
3 Correct 34 ms 2640 KB # of queries: 2978
4 Correct 37 ms 2676 KB # of queries: 2955
5 Correct 33 ms 2680 KB # of queries: 2966
6 Correct 33 ms 2664 KB # of queries: 2982
7 Correct 35 ms 2680 KB # of queries: 2974
8 Correct 23 ms 2680 KB # of queries: 2834
9 Correct 33 ms 2676 KB # of queries: 2937
10 Correct 21 ms 2676 KB # of queries: 1741
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 1 ms 2640 KB # of queries: 2
14 Correct 1 ms 2588 KB # of queries: 6
15 Correct 2 ms 2640 KB # of queries: 98
16 Correct 4 ms 2676 KB # of queries: 236
17 Correct 179 ms 2700 KB # of queries: 19588
18 Correct 270 ms 2812 KB # of queries: 19345
19 Correct 251 ms 2812 KB # of queries: 19550
20 Correct 245 ms 2700 KB # of queries: 18329
21 Correct 204 ms 2700 KB # of queries: 17196
22 Correct 266 ms 2708 KB # of queries: 19601
23 Correct 275 ms 2820 KB # of queries: 19532
24 Correct 109 ms 2688 KB # of queries: 9015
25 Correct 256 ms 2712 KB # of queries: 19139
26 Correct 253 ms 2684 KB # of queries: 17859
27 Correct 89 ms 2688 KB # of queries: 8992
28 Correct 248 ms 2708 KB # of queries: 17934
29 Correct 214 ms 2692 KB # of queries: 17914
30 Correct 243 ms 2704 KB # of queries: 17934