oj.uz

Submission #654362

# Submission time Handle Problem Language Result Execution time Memory
654362 2022-10-31T07:49:23 Z minhnhatnoe Library (JOI18_library) C++14
0 / 100
 47 ms 464 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;
    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:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i=0; i<chosen.size(); i++) chosen[i]++;
      |                   ~^~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 208 KB # of queries: 2373
2 Correct 47 ms 208 KB # of queries: 2417
3 Correct 34 ms 300 KB # of queries: 2630
4 Correct 36 ms 208 KB # of queries: 2601
5 Correct 35 ms 208 KB # of queries: 2466
6 Correct 43 ms 208 KB # of queries: 2551
7 Correct 33 ms 208 KB # of queries: 2578
8 Correct 42 ms 208 KB # of queries: 2414
9 Correct 24 ms 208 KB # of queries: 2512
10 Correct 20 ms 300 KB # of queries: 1474
11 Runtime error 3 ms 464 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 208 KB # of queries: 2373
2 Correct 47 ms 208 KB # of queries: 2417
3 Correct 34 ms 300 KB # of queries: 2630
4 Correct 36 ms 208 KB # of queries: 2601
5 Correct 35 ms 208 KB # of queries: 2466
6 Correct 43 ms 208 KB # of queries: 2551
7 Correct 33 ms 208 KB # of queries: 2578
8 Correct 42 ms 208 KB # of queries: 2414
9 Correct 24 ms 208 KB # of queries: 2512
10 Correct 20 ms 300 KB # of queries: 1474
11 Runtime error 3 ms 464 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -