oj.uz

Submission #230956

# Submission time Handle Problem Language Result Execution time Memory
230956 2020-05-12T07:14:42 Z AlexLuchianov Library (JOI18_library) C++14
100 / 100
 350 ms 536 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

int const nmax = 1000;

int pref[1 + nmax];

int _query(int x, int y, int n){
  vector<int> s(n);
  s[y - 1] = 1;
  for(int i = 0; i < x; i++)
    s[i] = 1;
  return (x + 1) - Query(s);
}

vector<int> g[1 + nmax];

void addedge(int x, int y){
  g[x].push_back(y);
  g[y].push_back(x);
}

void extractchain(int node, int parent, vector<int> &sol){
  sol.push_back(node);
  for(int h = 0; h < g[node].size(); h++){
    int to = g[node][h];
    if(to != parent)
      extractchain(to, node, sol);
  }
}

void Solve(int n)
{
  for(int i = 1; i <= n; i++){
    pref[i] = pref[i - 1];
    int x = 0;
    for(int jump = (1 << 10); 0 < jump; jump /= 2)
      if(x + jump < i && _query(x + jump, i, n) == pref[x + jump])
        x += jump;
    if(x + 1 < i){
      addedge(x + 1, i);
      pref[i]++;
      x++;
      for(int jump = (1 << 10); 0 < jump; jump /= 2)
        if(x + jump < i && _query(x + jump, i, n) == 1 + pref[x + jump])
          x += jump;
      if(x + 1 < i){
        addedge(x + 1, i);
        pref[i]++;
      }
    }
  }
  vector<int> res;
  for(int i = 1; i <= n; i++)
    if(g[i].size() < 2) {
      extractchain(i, 0, res);
      break;
    }
	Answer(res);
}

Compilation message

library.cpp: In function 'void extractchain(int, int, std::vector<int>&)':
library.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB # of queries: 1706
2 Correct 28 ms 384 KB # of queries: 1749
3 Correct 36 ms 384 KB # of queries: 1827
4 Correct 39 ms 384 KB # of queries: 1826
5 Correct 36 ms 384 KB # of queries: 1814
6 Correct 24 ms 400 KB # of queries: 1818
7 Correct 28 ms 384 KB # of queries: 1825
8 Correct 34 ms 384 KB # of queries: 1712
9 Correct 32 ms 384 KB # of queries: 1818
10 Correct 22 ms 384 KB # of queries: 1064
11 Correct 4 ms 384 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 4
14 Correct 5 ms 384 KB # of queries: 7
15 Correct 5 ms 384 KB # of queries: 59
16 Correct 6 ms 384 KB # of queries: 148

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 384 KB # of queries: 1706
2 Correct 28 ms 384 KB # of queries: 1749
3 Correct 36 ms 384 KB # of queries: 1827
4 Correct 39 ms 384 KB # of queries: 1826
5 Correct 36 ms 384 KB # of queries: 1814
6 Correct 24 ms 400 KB # of queries: 1818
7 Correct 28 ms 384 KB # of queries: 1825
8 Correct 34 ms 384 KB # of queries: 1712
9 Correct 32 ms 384 KB # of queries: 1818
10 Correct 22 ms 384 KB # of queries: 1064
11 Correct 4 ms 384 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 4
14 Correct 5 ms 384 KB # of queries: 7
15 Correct 5 ms 384 KB # of queries: 59
16 Correct 6 ms 384 KB # of queries: 148
17 Correct 330 ms 536 KB # of queries: 12128
18 Correct 322 ms 504 KB # of queries: 11966
19 Correct 305 ms 488 KB # of queries: 12097
20 Correct 311 ms 384 KB # of queries: 11275
21 Correct 280 ms 404 KB # of queries: 10650
22 Correct 350 ms 384 KB # of queries: 12109
23 Correct 297 ms 504 KB # of queries: 12141
24 Correct 125 ms 384 KB # of queries: 5527
25 Correct 299 ms 384 KB # of queries: 11844
26 Correct 271 ms 384 KB # of queries: 11061
27 Correct 120 ms 384 KB # of queries: 5520
28 Correct 156 ms 400 KB # of queries: 5923
29 Correct 170 ms 424 KB # of queries: 5915
30 Correct 164 ms 524 KB # of queries: 5923