Submission #131201

#	Time	Username	Problem	Language	Result	Execution time	Memory
131201		RezwanArefin01	Library (JOI18_library)	C++17	100 / 100	268 ms	504 KiB

library

#include <bits/stdc++.h>
#include "library.h"

using namespace std;

vector<vector<int>> comp; 
int N; 

vector<int> get(int l, int r) {
    vector<int> M(N, 0); 
    for(int i = l; i <= r; ++i) {
        for(int x : comp[i]) {
            M[x] = 1;
        }
    }
    return M; 
}


int find_comp(int u, int l, int r) {
    int lo = l, hi = r, ret;; 
    while(lo <= hi) {
        int mid = lo + hi >> 1; 

        vector<int> M = get(l, mid);  
        M[u] = 1; 

        if(Query(M) == mid - l + 1) {
            ret = mid; hi = mid - 1; 
        } else {
            lo = mid + 1;
        }
    }
    return ret; 
}

int find_side(int i, int c) {
    vector<int> M(N, 0); 
    M[i] = 1; 
    M[comp[c][0]] = 1; 

    if(Query(M) == 1) return 0; 
    else return 1; 
}

pair<int, int> find_merge(int u) {
    int lo = 0, hi = (int) comp.size() - 1;

    while(lo <= hi) {
        int mid = lo + hi >> 1; 

        vector<int> M = get(0, mid); 
        M[u] = 1; 

        int c = Query(M); 

        if(c == mid + 1) {
            return make_pair(find_comp(u, 0, mid), find_comp(u, mid + 1, (int) comp.size() - 1));
        } else if(c > mid + 1) {
            lo = mid + 1; 
        } else {
            hi = mid - 1;
        }
    }
    assert(0 == 1);
}

void Solve(int _N) {
    N = _N; 

    int C = 1;
    vector<int> M(N, 0); 
    M[0] = 1; 

    comp.push_back({0});

    for(int i = 1; i < N; ++i) {
        M[i] = 1; 
        int X = Query(M); 

        if(X > C) {
            comp.push_back({i}); 
        } else if(X == C) {
            int idx = find_comp(i, 0, (int) comp.size() - 1);
            int side = find_side(i, idx); 

            vector<int> &v = comp[idx]; 
            if(side) v.push_back(i); 
            else v.insert(v.begin(), i);  
        } else {
            int u, v; 
            tie(u, v) = find_merge(i);

            int su = find_side(i, u); 
            int sv = find_side(i, v); 

            if(su == 0) reverse(comp[u].begin(), comp[u].end());
            if(sv == 1) reverse(comp[v].begin(), comp[v].end()); 

            comp[u].push_back(i); 
            for(int x : comp[v]) {
                comp[u].push_back(x);
            }

            comp.erase(comp.begin() + v);
        } 

        C = X;
    }

    for(int &x : comp[0]) ++x; 
    Answer(comp[0]);
}

Compilation message (stderr)

library.cpp: In function 'int find_comp(int, int, int)':
library.cpp:23:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
library.cpp: In function 'std::pair<int, int> find_merge(int)':
library.cpp:50:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
library.cpp: In function 'int find_comp(int, int, int)':
library.cpp:34:12: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ret; 
            ^~~

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