Submission #874888

#	Time	Username	Problem	Language	Result	Execution time	Memory
874888		eu_caue	Library (JOI18_library)	C++14	0 / 100	6 ms	708 KiB

library

#include <bits/stdc++.h>
#include <library.h>
using namespace std;
const int maxn = 1005;

int l[maxn], r[maxn];
int pai1[maxn], pai2[maxn];
vector<int> heads1, heads2;

int find1(int x){
    return pai1[x] = pai1[x] == x ? x : find1(pai1[x]);
}

int find2(int x){
    return pai2[x] = pai2[x] == x ? x : find2(pai2[x]);
}

int Q1(int tl, int tr, int i, int n){
    if(tl == tr) return tl;
    int mid = (tl+tr)>>1;
    vector<int> q(n,0);
    for(int j = tl; j <= mid; j++) q[find1(heads1[j])-1] = 1;
    q[i-1] = 1;
    int f = Query(q);
    if(f == heads1.size()) return Q1(tl, mid, i, n);
    return Q1(mid+1, tr, i, n);
}

int Q2(int tl, int tr, int i, int n){
    if(tl == tr) return tl;
    int mid = (tl+tr)>>1;
    vector<int> q(n,0);
    for(int j = tl; j <= mid; j++) q[find2(heads2[j])-1] = 1;
    q[i-1] = 1;
    int f = Query(q);
    if(f == heads2.size()) return Q2(tl, mid, i, n);
    return Q2(mid+1, tr, i, n);
}

void Solve(int n){
    for(int i = 1; i <= n; i++) pai1[i] = pai2[i] = i;
    memset(l, -1, sizeof(l)), memset(r, -1, sizeof(r));
    for(int i = 1; i <= n; i++){
        vector<int> q1(n,0);
        for(auto j : heads1) q1[find2(j)-1] = 1;
        q1[i-1] = 1;
        int f = Query(q1);
        if(f == heads1.size()+1){
            heads1.push_back(i);
        }
        else{
            int v = Q1(0, heads1.size(), i, n);
            l[heads1[v]] = pai1[heads1[v]] = i;
            heads1[v] = i;
        }
        // vector<int> q2(n,0);
        // for(auto j : heads2) q2[find1(j)-1] = 1;
        // q2[i-1] = 1;
        // f = Query(q2);
        // if(f == heads2.size()+1){
        //     heads2.push_back(i);
        // }
        // else{
        //     int v = Q1(0, heads1.size(), i, n);
        //     l[heads2[v]] = pai1[heads2[v]] = i;
        //     heads2[v] = i;
        // }
    }
    int s;
    for(int i = 1; i <= n; i++) if(l[i] == -1) s = i;
    vector<int> ans(n);
    ans[0] = s;
    for(int i = 1; i < n; i++) ans[i] = l[ans[i-1]];
    Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'int Q1(int, int, int, int)':
library.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if(f == heads1.size()) return Q1(tl, mid, i, n);
      |        ~~^~~~~~~~~~~~~~~~
library.cpp: In function 'int Q2(int, int, int, int)':
library.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(f == heads2.size()) return Q2(tl, mid, i, n);
      |        ~~^~~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if(f == heads1.size()+1){
      |            ~~^~~~~~~~~~~~~~~~~~
library.cpp:72:12: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |     ans[0] = s;

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81