Submission #50145

#	Time	Username	Problem	Language	Result	Execution time	Memory
50145		spencercompton	Library (JOI18_library)	C++17	100 / 100	568 ms	716 KiB

library

#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n;
vector<vector<int> > li;
vector<int> rev(vector<int> a){
    vector<int> ret;
    for(int i = a.size()-1; i>=0; i--){
        ret.push_back(a[i]);
    }
    return ret;
}
void join(int a, int b){
    vector<vector<int> > nex;
    for(int i = 0; i<li.size(); i++){
        if(i==a || i==b){
            continue;
        }
        nex.push_back(li[i]);
    }
    for(int i = 0; i<li[b].size(); i++){
        li[a].push_back(li[b][i]);
    }
    nex.push_back(li[a]);
    li = nex;
}
bool get(int a, int b){
    vector<int> use;
    use.resize(n);
    for(int i = a; i<=b; i++){
        for(int j = 0; j<li[i].size(); j++){
            use[li[i][j]] = 1;
        }
    }
    return Query(use)!=(b-a+1);
}
bool get2(int val, int loc){
    vector<int> use;
    use.resize(n);
    use[val] = 1;
    for(int i = 0; i<li[loc].size(); i++){
        use[li[loc][i]] = 1;
    }
    return Query(use)==1;
}
void Solve(int N)
{
    n = N;
// 	vector<int> M(N);
// 	int A = Query(M);
// 	vector<int> res(N);
//     Answer(res);
    for(int i =0; i<N; i++){
        vector<int> x;
        x.push_back(i);
        li.push_back(x);
    }
    while(li.size()>1){
        int low = 1;
        int high = li.size()-1;
        while(low<high){
            int mid = (low+high)/2;
            if(get(0,mid)){
                high = mid;
            }
            else{
                low = mid+1;
            }
        }
        int r = low;
        low = 0;
        high = r-1;
        while(low<high){
            int mid = (low+high+1)/2;
            if(get(mid,r)){
                low = mid;
            }
            else{
                high = mid-1;
            }
        }
        int l = low;
        bool leftFirst = get2(li[l][li[l].size()-1],r);
        if(leftFirst){
            bool needRev = get2(li[r][li[r].size()-1],l);
            if(needRev){
                li[r] = rev(li[r]);
            }
            join(l,r);
        }
        else{
            bool needRev = get2(li[r][0],l);
            if(needRev){
                li[r] = rev(li[r]);
            }
            join(r,l);
        }
    }
    vector<int> ans;
    for(int i = 0; i<li[0].size(); i++){
        ans.push_back(li[0][i]+1);
    }
    Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'void join(int, int)':
library.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<li.size(); i++){
                    ~^~~~~~~~~~
library.cpp:23:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<li[b].size(); i++){
                    ~^~~~~~~~~~~~~
library.cpp: In function 'bool get(int, int)':
library.cpp:33:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j<li[i].size(); j++){
                        ~^~~~~~~~~~~~~
library.cpp: In function 'bool get2(int, int)':
library.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<li[loc].size(); i++){
                    ~^~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<li[0].size(); i++){
                    ~^~~~~~~~~~~~~

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