oj.uz

Submission #122900

# Submission time Handle Problem Language Result Execution time Memory
122900 2019-06-29T13:43:11 Z Gustav Library (JOI18_library) C++14
0 / 100
 588 ms 408 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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 248 KB Wrong Answer [5]
2 Incorrect 57 ms 248 KB Wrong Answer [5]
3 Incorrect 53 ms 376 KB Wrong Answer [5]
4 Incorrect 37 ms 376 KB Wrong Answer [5]
5 Incorrect 36 ms 248 KB Wrong Answer [5]
6 Incorrect 37 ms 248 KB Wrong Answer [5]
7 Incorrect 48 ms 376 KB Wrong Answer [5]
8 Incorrect 53 ms 248 KB Wrong Answer [5]
9 Incorrect 50 ms 376 KB Wrong Answer [5]
10 Incorrect 20 ms 376 KB Wrong Answer [5]
11 Incorrect 2 ms 248 KB Wrong Answer [5]
12 Incorrect 2 ms 380 KB Wrong Answer [5]
13 Incorrect 2 ms 376 KB Wrong Answer [5]
14 Incorrect 2 ms 252 KB Wrong Answer [5]
15 Incorrect 4 ms 380 KB Wrong Answer [5]
16 Incorrect 4 ms 248 KB Wrong Answer [5]

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 248 KB Wrong Answer [5]
2 Incorrect 57 ms 248 KB Wrong Answer [5]
3 Incorrect 53 ms 376 KB Wrong Answer [5]
4 Incorrect 37 ms 376 KB Wrong Answer [5]
5 Incorrect 36 ms 248 KB Wrong Answer [5]
6 Incorrect 37 ms 248 KB Wrong Answer [5]
7 Incorrect 48 ms 376 KB Wrong Answer [5]
8 Incorrect 53 ms 248 KB Wrong Answer [5]
9 Incorrect 50 ms 376 KB Wrong Answer [5]
10 Incorrect 20 ms 376 KB Wrong Answer [5]
11 Incorrect 2 ms 248 KB Wrong Answer [5]
12 Incorrect 2 ms 380 KB Wrong Answer [5]
13 Incorrect 2 ms 376 KB Wrong Answer [5]
14 Incorrect 2 ms 252 KB Wrong Answer [5]
15 Incorrect 4 ms 380 KB Wrong Answer [5]
16 Incorrect 4 ms 248 KB Wrong Answer [5]
17 Incorrect 561 ms 328 KB Wrong Answer [5]
18 Incorrect 583 ms 376 KB Wrong Answer [5]
19 Incorrect 588 ms 376 KB Wrong Answer [5]
20 Incorrect 530 ms 248 KB Wrong Answer [5]
21 Incorrect 506 ms 376 KB Wrong Answer [5]
22 Incorrect 586 ms 380 KB Wrong Answer [5]
23 Incorrect 587 ms 376 KB Wrong Answer [5]
24 Incorrect 215 ms 408 KB Wrong Answer [5]
25 Incorrect 565 ms 376 KB Wrong Answer [5]
26 Incorrect 539 ms 248 KB Wrong Answer [5]
27 Incorrect 201 ms 376 KB Wrong Answer [5]
28 Incorrect 525 ms 248 KB Wrong Answer [5]
29 Incorrect 526 ms 376 KB Wrong Answer [5]
30 Incorrect 523 ms 376 KB Wrong Answer [5]