oj.uz

Submission #108843

# Submission time Handle Problem Language Result Execution time Memory
108843 2019-05-02T09:43:33 Z tictaccat Library (JOI18_library) C++14
0 / 100
 622 ms 608 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);

bool check(int j, int i) { //does (i->j) contain a not known pair?
    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;

  //  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 = high/2; b > 0; b /= 2){
            while (i + b < high && !check(0,i+b)) i += b;
        }
        i++;
        int j = 0; high = i;
        for (int b = high/2; b > 0; b /= 2) {
            while (j + b < high && check(j+b,i)) {j += b;}
        }
        known.emplace_back(j,i);
        pairs[j].push_back(i);
        pairs[i].push_back(j);
    }

    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:52: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 Correct 60 ms 384 KB # of queries: 3685
2 Correct 56 ms 384 KB # of queries: 3909
3 Correct 63 ms 348 KB # of queries: 3871
4 Correct 52 ms 456 KB # of queries: 3903
5 Correct 61 ms 344 KB # of queries: 3894
6 Correct 71 ms 256 KB # of queries: 3884
7 Correct 66 ms 344 KB # of queries: 3934
8 Correct 43 ms 432 KB # of queries: 4011
9 Correct 44 ms 348 KB # of queries: 4170
10 Correct 23 ms 432 KB # of queries: 2499
11 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 2 ms 384 KB # of queries: 1
13 Correct 3 ms 384 KB # of queries: 4
14 Correct 2 ms 384 KB # of queries: 12
15 Correct 4 ms 384 KB # of queries: 134
16 Correct 6 ms 384 KB # of queries: 315

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 384 KB # of queries: 3685
2 Correct 56 ms 384 KB # of queries: 3909
3 Correct 63 ms 348 KB # of queries: 3871
4 Correct 52 ms 456 KB # of queries: 3903
5 Correct 61 ms 344 KB # of queries: 3894
6 Correct 71 ms 256 KB # of queries: 3884
7 Correct 66 ms 344 KB # of queries: 3934
8 Correct 43 ms 432 KB # of queries: 4011
9 Correct 44 ms 348 KB # of queries: 4170
10 Correct 23 ms 432 KB # of queries: 2499
11 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 2 ms 384 KB # of queries: 1
13 Correct 3 ms 384 KB # of queries: 4
14 Correct 2 ms 384 KB # of queries: 12
15 Correct 4 ms 384 KB # of queries: 134
16 Correct 6 ms 384 KB # of queries: 315
17 Incorrect 512 ms 476 KB Wrong Answer [3]
18 Incorrect 556 ms 476 KB Wrong Answer [3]
19 Incorrect 531 ms 472 KB Wrong Answer [3]
20 Incorrect 622 ms 596 KB Wrong Answer [3]
21 Incorrect 573 ms 344 KB Wrong Answer [3]
22 Incorrect 587 ms 476 KB Wrong Answer [3]
23 Incorrect 514 ms 376 KB Wrong Answer [3]
24 Correct 230 ms 388 KB # of queries: 13027
25 Incorrect 582 ms 608 KB Wrong Answer [3]
26 Incorrect 569 ms 604 KB Wrong Answer [3]
27 Correct 266 ms 468 KB # of queries: 12472
28 Correct 461 ms 376 KB # of queries: 16114
29 Correct 502 ms 604 KB # of queries: 16958
30 Correct 440 ms 516 KB # of queries: 16114