Submission #108844

#	Time	Username	Problem	Language	Result	Execution time	Memory
108844		tictaccat	Library (JOI18_library)	C++14	19 / 100	647 ms	604 KiB

library

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

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