Submission #230956

#	Time	Username	Problem	Language	Result	Execution time	Memory
230956		AlexLuchianov	Library (JOI18_library)	C++14	100 / 100	350 ms	536 KiB

library

#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 (stderr)

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 / 19
• Subtask 2: 81 / 81