Submission #624086

#	Time	Username	Problem	Language	Result	Execution time	Memory
624086		radal	Library (JOI18_library)	C++17	100 / 100	287 ms	328 KiB

library

#include <bits/stdc++.h>
#include "library.h"
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e3+10,mod = 998244353,inf = 1e9+10;
int moj[N][2];
void Solve(int n){
    if (n == 1){
        vector<int> ve;
        ve.pb(1);
        Answer(ve);
        return;
    }
    memset(moj,-1,sizeof moj);
    vector<int> ask;
    ask.resize(n);
    rep(i,1,n+1){
        if (moj[i][0] != -1 && moj[i][1] != -1) continue;
        if (moj[i][0] != -1){
            int v = moj[i][0];
            rep(j,0,v){
                if (j == i-1) continue;
                ask[j] = 1;
            }
            rep(j,v,n) ask[j] = 0;
            int x = Query(ask);
            ask[i-1] = 1;
            int y = Query(ask);
            if (y-x == -1){
                int l = i,r = v-1,m;
                while (r-l > 1){
                    m = (l+r) >> 1;
                    ask[i-1] = 0;
                    rep(j,0,m){
                        if (j == i-1) continue;
                        ask[j] = 1;
                    }
                    rep(j,m,n) ask[j] = 0;
                    x = Query(ask);
                    ask[i-1] = 1;
                    y = Query(ask);
                    if (y-x > 0) l = m;
                    else r = m;
                }
                moj[i][1] = r;
                if (moj[r][0] == -1) moj[r][0] = i;
                else moj[r][1] = i;
                continue;
            }
            int l = v,r = n+1,m;
            while (r-l > 1){
                m = (l+r) >> 1;
                ask[i-1] = 0;
                rep(j,0,m){
                    if (j == i-1) continue;
                    ask[j] = 1;
                }
                rep(j,m,n) ask[j] = 0;
                x = Query(ask);
                ask[i-1] = 1;
                y = Query(ask);
                if (y-x == 0) l = m;
                else r = m;
            }
            if (r == n+1) continue;
            moj[i][1] = r;
            if (moj[r][0] == -1) moj[r][0] = i;
            else moj[r][1] = i;
            continue;
        }
        int l = i,r = n+1,m,r2 = n+1,x,y;
        while (r-l > 1){
            m = (l+r) >> 1;
            ask[i-1] = 0;
            rep(j,0,m){
                if (j == i-1) continue;
                ask[j] = 1;
            }
            rep(j,m,n) ask[j] = 0;
            x = Query(ask);
            ask[i-1] = 1;
            y = Query(ask);
            if (y-x == 1) l = m;
            else{
                r = m;
                if (y-x == -1) r2 = m;
            }
        }
        moj[i][0] = r;
        if (moj[r][0] == -1) moj[r][0] = i;
        else moj[r][1] = i;
        l = r;
        r = r2;
        while (r-l > 1){ 
            m = (l+r) >> 1;
            ask[i-1] = 0;
            rep(j,0,m){
                if (j == i-1) continue;
                ask[j] = 1;
            }
            rep(j,m,n) ask[j] = 0;
            x = Query(ask);
            ask[i-1] = 1;
            y = Query(ask);
            if (y-x == 0) l = m;
            else r = m;
        }
        if (r == n+1) continue;
        moj[i][1] = r;
        if (moj[r][0] == -1) moj[r][0] = i;
        else moj[r][1] = i;
    }
    vector<int> ans;
    int cur = 1,perv = -1;
    rep(i,1,n+1) if (moj[i][1] == -1) cur = i;
    while (cur > 0){
        ans.pb(cur);
        if (ans.size() == n) break;
        if (moj[cur][0] == perv){
            perv = cur;
            cur = moj[cur][1];
        }
        else{
            perv = cur;
            cur = moj[cur][0];
        }
    }
    Answer(ans);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:131:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |         if (ans.size() == n) break;
      |             ~~~~~~~~~~~^~~~

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