Submission #874594

#	Time	Username	Problem	Language	Result	Execution time	Memory
874594		garam1732	Library (JOI18_library)	C++14	100 / 100	314 ms	596 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;

//#include <iostream>

vector<int> res, v;

void Solve(int n)
{
    for(int i = 0; i < n; i++) res.push_back(i);
    v.resize(n);

	int s = 0, e = n-1;
	while(s < e) {
        //cout << s<<' '<<e<<endl;
        //for(int x : res) cout<<x<<' ';
        //cout<<endl;
        int lb = s, ub = e, mid;
        while(lb < ub) {
            mid = lb+ub>>1;

            for(int i = 0; i < n; i++) v[res[i]] = (lb <= i && i <= mid);
            int x = Query(v);
            for(int i = s; i <= e; i++) v[res[i]] ^= 1;
            int y = Query(v);

            if(x >= y) ub = mid;
            else lb = mid+1;
        }

        //cout<<res[lb]<<endl;

        if(s > 0) {
            for(int i = 0; i < n; i++) v[i] = (i == res[s-1] || i == res[lb]);
            int x = Query(v);
            if(x == 1) swap(res[s++], res[lb]);
            else swap(res[e--], res[lb]);
        }
        else if(e < n-1) {
            for(int i = 0; i < n; i++) v[i] = (i == res[e+1] || i == res[lb]);
            int x = Query(v);
            if(x == 1) swap(res[e--], res[lb]);
            else swap(res[s++], res[lb]);
        }
        else swap(res[s++], res[lb]);
	}

	for(int &x : res) x++;
	Answer(res);
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             mid = lb+ub>>1;
      |                   ~~^~~

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