oj.uz

Submission #654365

# Submission time Handle Problem Language Result Execution time Memory
654365 2022-10-31T07:55:26 Z minhnhatnoe Library (JOI18_library) C++14
100 / 100
 468 ms 328 KB 
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

int find_edge(int n){
    vector<int> a(n, 1);
    for (int i=0; i<n; i++){
        a[i] = 0;
        if (Query(a) == 1) return i;
        a[i] = 1;
    }
    throw runtime_error("Unreachable");
}
vector<int> binsearch(int n, vector<int> &a, vector<int> &chosen){
    vector<int> q(n);
    for (int i=a.size()/2-1; i>=0; i--) q[a[i]] = 1;
    int f = Query(q);
    for (int i: chosen) q[i] = 1;
    int s = Query(q);
    if (f == s){
        vector<int> nxt;
        for (int i=a.size()/2-1; i>=0; i--) nxt.push_back(a[i]);
        return nxt;
    }
    else{
        vector<int> nxt;
        for (int i=a.size()/2; i<a.size(); i++) nxt.push_back(a[i]);
        return nxt;
    }
}
vector<int> inverse(int n, vector<int> &chosen){
    vector<bool> a(n, 1);
    for (int i: chosen) a[i] = false;
    vector<int> nxt;
    for (int i=0; i<a.size(); i++) if (a[i]) nxt.push_back(i);
    return nxt;
}
void Solve(int N){
    int n = N;
    if (n == 1){
        Answer({1});
        return;
    }
    int left = find_edge(n);
    // cout << "LEFT: " << left+1 << " ";
    vector<int> chosen = {left};
    for (int i=1; i<n; i++){
        vector<int> cand = inverse(n, chosen);
        while (cand.size() != 1){
            cand = binsearch(n, cand, chosen);
        }
        // cout << "CHOSE: " << cand[0] + 1 << " ";
        chosen.push_back(cand[0]);
    }
    for (int i=0; i<chosen.size(); i++) chosen[i]++;
    Answer(chosen);
}

Compilation message

library.cpp: In function 'std::vector<int> binsearch(int, std::vector<int>&, std::vector<int>&)':
library.cpp:27:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int i=a.size()/2; i<a.size(); i++) nxt.push_back(a[i]);
      |                                ~^~~~~~~~~
library.cpp: In function 'std::vector<int> inverse(int, std::vector<int>&)':
library.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i=0; i<a.size(); i++) if (a[i]) nxt.push_back(i);
      |                   ~^~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0; i<chosen.size(); i++) chosen[i]++;
      |                   ~^~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 208 KB # of queries: 2373
2 Correct 31 ms 208 KB # of queries: 2417
3 Correct 36 ms 300 KB # of queries: 2630
4 Correct 35 ms 208 KB # of queries: 2601
5 Correct 23 ms 296 KB # of queries: 2466
6 Correct 34 ms 284 KB # of queries: 2551
7 Correct 33 ms 208 KB # of queries: 2578
8 Correct 36 ms 208 KB # of queries: 2414
9 Correct 34 ms 208 KB # of queries: 2512
10 Correct 18 ms 208 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 1 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 79
16 Correct 3 ms 208 KB # of queries: 185

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 208 KB # of queries: 2373
2 Correct 31 ms 208 KB # of queries: 2417
3 Correct 36 ms 300 KB # of queries: 2630
4 Correct 35 ms 208 KB # of queries: 2601
5 Correct 23 ms 296 KB # of queries: 2466
6 Correct 34 ms 284 KB # of queries: 2551
7 Correct 33 ms 208 KB # of queries: 2578
8 Correct 36 ms 208 KB # of queries: 2414
9 Correct 34 ms 208 KB # of queries: 2512
10 Correct 18 ms 208 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 1 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 79
16 Correct 3 ms 208 KB # of queries: 185
17 Correct 439 ms 292 KB # of queries: 18024
18 Correct 398 ms 300 KB # of queries: 17255
19 Correct 449 ms 292 KB # of queries: 17515
20 Correct 334 ms 288 KB # of queries: 16317
21 Correct 298 ms 288 KB # of queries: 15294
22 Correct 430 ms 300 KB # of queries: 17643
23 Correct 415 ms 288 KB # of queries: 17186
24 Correct 178 ms 288 KB # of queries: 7889
25 Correct 423 ms 328 KB # of queries: 17098
26 Correct 371 ms 292 KB # of queries: 16019
27 Correct 155 ms 300 KB # of queries: 8026
28 Correct 452 ms 292 KB # of queries: 17917
29 Correct 468 ms 328 KB # of queries: 17897
30 Correct 398 ms 288 KB # of queries: 17917