oj.uz

Submission #108844

# Submission time Handle Problem Language Result Execution time Memory
108844 2019-05-02T09:45:06 Z tictaccat Library (JOI18_library) C++14
19 / 100
 647 ms 604 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;

    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 = 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:57: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 60 ms 384 KB # of queries: 3685
2 Correct 72 ms 384 KB # of queries: 3909
3 Correct 61 ms 384 KB # of queries: 3871
4 Correct 70 ms 384 KB # of queries: 3903
5 Correct 70 ms 256 KB # of queries: 3894
6 Correct 64 ms 384 KB # of queries: 3884
7 Correct 51 ms 344 KB # of queries: 3934
8 Correct 56 ms 348 KB # of queries: 4011
9 Correct 119 ms 256 KB # of queries: 4170
10 Correct 40 ms 256 KB # of queries: 2499
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 1
13 Correct 2 ms 256 KB # of queries: 4
14 Correct 2 ms 384 KB # of queries: 12
15 Correct 5 ms 384 KB # of queries: 134
16 Correct 8 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 72 ms 384 KB # of queries: 3909
3 Correct 61 ms 384 KB # of queries: 3871
4 Correct 70 ms 384 KB # of queries: 3903
5 Correct 70 ms 256 KB # of queries: 3894
6 Correct 64 ms 384 KB # of queries: 3884
7 Correct 51 ms 344 KB # of queries: 3934
8 Correct 56 ms 348 KB # of queries: 4011
9 Correct 119 ms 256 KB # of queries: 4170
10 Correct 40 ms 256 KB # of queries: 2499
11 Correct 2 ms 384 KB # of queries: 0
12 Correct 2 ms 256 KB # of queries: 1
13 Correct 2 ms 256 KB # of queries: 4
14 Correct 2 ms 384 KB # of queries: 12
15 Correct 5 ms 384 KB # of queries: 134
16 Correct 8 ms 384 KB # of queries: 315
17 Incorrect 607 ms 380 KB Wrong Answer [3]
18 Incorrect 558 ms 376 KB Wrong Answer [3]
19 Incorrect 544 ms 600 KB Wrong Answer [3]
20 Incorrect 605 ms 376 KB Wrong Answer [3]
21 Incorrect 588 ms 552 KB Wrong Answer [3]
22 Incorrect 603 ms 504 KB Wrong Answer [3]
23 Incorrect 569 ms 480 KB Wrong Answer [3]
24 Correct 259 ms 352 KB # of queries: 13027
25 Incorrect 647 ms 604 KB Wrong Answer [3]
26 Incorrect 578 ms 376 KB Wrong Answer [3]
27 Correct 260 ms 356 KB # of queries: 12472
28 Correct 422 ms 424 KB # of queries: 16114
29 Correct 466 ms 424 KB # of queries: 16958
30 Correct 489 ms 380 KB # of queries: 16114