oj.uz

Submission #122902

# Submission time Handle Problem Language Result Execution time Memory
122902 2019-06-29T13:44:53 Z Gustav Library (JOI18_library) C++14
100 / 100
 612 ms 420 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())
 
int n;
vi found(1010);
 
/*
int Query(const std::vector<int>& M){
    cout << "Query: ";
    for(int i = 0; i < sz(M); i++) cout << M[i] << " ";
    cout << endl;
    int r;
    cin >> r;
    return r;
}
 
void Answer(const std::vector<int>& res)
{
    cout << "Answer: ";
    for(int i = 0; i < sz(res); i++) cout << res[i] << " ";
    cout << endl;
}
*/
 
int endcount(vi o){
    vi m(n);
    for(int i = 0; i < sz(o); i++){
        m[o[i]] = 1;
    }
    int r1 = Query(m);
    for(int i = 0; i < n; i++){
        if(m[i]) m[i] = 0;
        else if(!found[i]) m[i] = 1;
    }
    int r2 = Query(m);
    if(r1 == r2) return 1;
    if(r1+1 == r2) return 0;
    if(r1 == r2+1) return 2;
    assert(false);
    return -1;
}
 
int find(){
    vi left;
    for(int i = 0; i < n; i++){
        if(!found[i]) left.push_back(i);
    }
 
    int lo = 0, hi = sz(left);
    while(lo+1 < hi){
        int mid = (lo+hi)/2;
        vi c;
        for(int i = 0; i < mid; i++){
            c.push_back(left[i]);
        }
        int r = endcount(c);
        if(r == 0) lo = mid;
        else hi = mid;
    }
    return left[lo];
}
 
void Solve(int N){
    n = N;
 
    vi start;
    vi end;
    start.push_back(find());
    found[start[0]] = 1;
    for(int i = 0; i < n-1; i++){
        int r = find();
        found[r] = 1;
        vi t(n);
        t[r] = 1;
        t[start[sz(start)-1]] = 1;
        if(Query(t) == 1) start.push_back(r);
        else end.push_back(r);
    }
    for(int i = sz(end)-1; i >= 0; i--){
        start.push_back(end[i]);
    }
    for(int i = 0; i < sz(start); i++) start[i]++;
    Answer(start);
}
 
/*
int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
 
    Solve(5);
}
*/

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 248 KB # of queries: 2581
2 Correct 52 ms 248 KB # of queries: 2564
3 Correct 51 ms 248 KB # of queries: 2677
4 Correct 42 ms 248 KB # of queries: 2707
5 Correct 54 ms 376 KB # of queries: 2703
6 Correct 37 ms 248 KB # of queries: 2697
7 Correct 52 ms 372 KB # of queries: 2723
8 Correct 53 ms 376 KB # of queries: 2580
9 Correct 56 ms 376 KB # of queries: 2678
10 Correct 29 ms 376 KB # of queries: 1572
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 3
13 Correct 2 ms 248 KB # of queries: 8
14 Correct 2 ms 248 KB # of queries: 13
15 Correct 3 ms 376 KB # of queries: 92
16 Correct 6 ms 248 KB # of queries: 212

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 248 KB # of queries: 2581
2 Correct 52 ms 248 KB # of queries: 2564
3 Correct 51 ms 248 KB # of queries: 2677
4 Correct 42 ms 248 KB # of queries: 2707
5 Correct 54 ms 376 KB # of queries: 2703
6 Correct 37 ms 248 KB # of queries: 2697
7 Correct 52 ms 372 KB # of queries: 2723
8 Correct 53 ms 376 KB # of queries: 2580
9 Correct 56 ms 376 KB # of queries: 2678
10 Correct 29 ms 376 KB # of queries: 1572
11 Correct 2 ms 376 KB # of queries: 0
12 Correct 2 ms 376 KB # of queries: 3
13 Correct 2 ms 248 KB # of queries: 8
14 Correct 2 ms 248 KB # of queries: 13
15 Correct 3 ms 376 KB # of queries: 92
16 Correct 6 ms 248 KB # of queries: 212
17 Correct 558 ms 420 KB # of queries: 18153
18 Correct 576 ms 328 KB # of queries: 17978
19 Correct 558 ms 376 KB # of queries: 18101
20 Correct 535 ms 248 KB # of queries: 16945
21 Correct 465 ms 328 KB # of queries: 15944
22 Correct 612 ms 248 KB # of queries: 18173
23 Correct 602 ms 416 KB # of queries: 18108
24 Correct 164 ms 376 KB # of queries: 8334
25 Correct 537 ms 344 KB # of queries: 17744
26 Correct 501 ms 248 KB # of queries: 16508
27 Correct 203 ms 412 KB # of queries: 8282
28 Correct 507 ms 416 KB # of queries: 16973
29 Correct 500 ms 252 KB # of queries: 16954
30 Correct 480 ms 248 KB # of queries: 16973