oj.uz

Submission #108849

# Submission time Handle Problem Language Result Execution time Memory
108849 2019-05-02T09:52:21 Z tictaccat Library (JOI18_library) C++14
0 / 100
 231 ms 616 KB 
#include <cstdio>
#include <vector>
#include "library.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000+10;

int N;
vector<pair<int,int>> known;
vector<vector<int>> pairs(MAX+10);
int queries = 0;

bool check(int j, int i) { //does (i->j) contain a not known pair?
    queries++;
    int already = 0;
    for (auto p: known) {
        if (j <= p.first && p.first <= i && j <= p.second && p.second <= i) already++;
    }
    vector<int> M(N,0);
    for (int k = j; k <= i; k++) M[k] = 1;
    return ((i-j+1)-Query(M) != already);
}

void Solve(int Nt)
{

    N = Nt;

    if (N == 1) {
		Answer(vector<int>{1});
		return;
	}

  //  cout << check(0,1) << "\n";

 //   cout << check(1,2) << "\n";    

	while ((int)known.size() < N-1) {
        int i = 0; int high = N;
        for (int b = (1<<(int)log2(high)); b > 0; b /= 2){
            if (i + b < high && !check(0,i+b)) i += b;
        }
        i++;
        int j = 0; high = i;
        for (int b = (1<<(int)log2(high)); b > 0; b /= 2) {
            if (j + b < high && check(j+b,i)) {j += b;}
        }
        known.emplace_back(j,i);
        pairs[j].push_back(i);
        pairs[i].push_back(j);
        cout << queries << "\n";
    }

    int end;
    for (int i = 0; i < N; i++) if (pairs[i].size() == 1) {end = i; break;}

    vector<int> seq {end};
    vector<bool> found(N,false);
    found[end] = true;

    for (int k = 0; k < N-1; k++) {
        for (int nxt: pairs[end]) {
            if (found[nxt]) continue;
            seq.push_back(nxt);
            found[nxt] = true;
            end = nxt;
        }
    }

    //for (int e: seq) cout << e+1 << " "; cout << "\n";
    for (int &e: seq) e++;
    Answer(seq);

}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:60:14: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
     found[end] = true;
              ^

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
2 Incorrect 9 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
3 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
4 Incorrect 12 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
5 Incorrect 14 ms 348 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
6 Incorrect 10 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
7 Incorrect 10 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
8 Incorrect 9 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
9 Incorrect 15 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
10 Incorrect 6 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
11 Correct 2 ms 384 KB # of queries: 0
12 Incorrect 3 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
13 Runtime error 2 ms 560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
15 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
16 Incorrect 2 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
2 Incorrect 9 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
3 Incorrect 9 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
4 Incorrect 12 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
5 Incorrect 14 ms 348 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
6 Incorrect 10 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
7 Incorrect 10 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
8 Incorrect 9 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
9 Incorrect 15 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
10 Incorrect 6 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
11 Correct 2 ms 384 KB # of queries: 0
12 Incorrect 3 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
13 Runtime error 2 ms 560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
15 Incorrect 2 ms 256 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
16 Incorrect 2 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
17 Incorrect 194 ms 432 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
18 Incorrect 195 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
19 Incorrect 173 ms 424 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
20 Incorrect 162 ms 360 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
21 Incorrect 142 ms 480 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
22 Incorrect 170 ms 372 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
23 Incorrect 217 ms 476 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
24 Incorrect 48 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
25 Incorrect 166 ms 376 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
26 Incorrect 160 ms 476 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
27 Incorrect 52 ms 424 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
28 Incorrect 190 ms 380 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
29 Incorrect 231 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
30 Incorrect 206 ms 616 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT