oj.uz

Submission #108851

# Submission time Handle Problem Language Result Execution time Memory
108851 2019-05-02T09:53:08 Z tictaccat Library (JOI18_library) C++11
100 / 100
 564 ms 488 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
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 344 KB # of queries: 2794
2 Correct 48 ms 340 KB # of queries: 2788
3 Correct 35 ms 428 KB # of queries: 2998
4 Correct 45 ms 348 KB # of queries: 2975
5 Correct 63 ms 384 KB # of queries: 2977
6 Correct 42 ms 384 KB # of queries: 2981
7 Correct 43 ms 348 KB # of queries: 2977
8 Correct 37 ms 256 KB # of queries: 2891
9 Correct 50 ms 344 KB # of queries: 3000
10 Correct 25 ms 344 KB # of queries: 1853
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 1
13 Correct 2 ms 256 KB # of queries: 5
14 Correct 2 ms 256 KB # of queries: 10
15 Correct 4 ms 256 KB # of queries: 100
16 Correct 3 ms 256 KB # of queries: 242

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 344 KB # of queries: 2794
2 Correct 48 ms 340 KB # of queries: 2788
3 Correct 35 ms 428 KB # of queries: 2998
4 Correct 45 ms 348 KB # of queries: 2975
5 Correct 63 ms 384 KB # of queries: 2977
6 Correct 42 ms 384 KB # of queries: 2981
7 Correct 43 ms 348 KB # of queries: 2977
8 Correct 37 ms 256 KB # of queries: 2891
9 Correct 50 ms 344 KB # of queries: 3000
10 Correct 25 ms 344 KB # of queries: 1853
11 Correct 2 ms 256 KB # of queries: 0
12 Correct 2 ms 384 KB # of queries: 1
13 Correct 2 ms 256 KB # of queries: 5
14 Correct 2 ms 256 KB # of queries: 10
15 Correct 4 ms 256 KB # of queries: 100
16 Correct 3 ms 256 KB # of queries: 242
17 Correct 454 ms 384 KB # of queries: 19422
18 Correct 525 ms 436 KB # of queries: 19186
19 Correct 428 ms 352 KB # of queries: 19407
20 Correct 439 ms 384 KB # of queries: 18157
21 Correct 461 ms 356 KB # of queries: 17029
22 Correct 476 ms 380 KB # of queries: 19428
23 Correct 475 ms 488 KB # of queries: 19407
24 Correct 157 ms 348 KB # of queries: 9455
25 Correct 564 ms 352 KB # of queries: 18975
26 Correct 469 ms 376 KB # of queries: 17759
27 Correct 178 ms 352 KB # of queries: 8941
28 Correct 436 ms 352 KB # of queries: 14900
29 Correct 434 ms 468 KB # of queries: 14885
30 Correct 468 ms 384 KB # of queries: 14900