제출 #508787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508787		kevinxiehk	도서관 (JOI18_library)	C++17	100 / 100	313 ms	416 KiB

library

#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

void Solve(int n) {
	vector<int> M(n);
    vector<int> res;
    if(n == 1) {
        res.pb(1);
        Answer(res);
        return;
    }
    vector<pair<int, int>> tmp;
	for(int i = 0; i < n; i++) {
		M[i] = 1;
        tmp.pb(mp(0, i));
	}
    for(int i = 0; i < n; i++) {
        M[i] = 0;
        int t = Query(M);
        M[i] = 1;
        if(t == 1) {
            res.pb(i);
            tmp[i].fi = 1;
            break;
        }
    }

    for(int lef = n - 1; lef >= 2; lef--) {
        sort(tmp.begin(), tmp.end());
        int hm = res[res.size() - 1];
        int l = 0, r = lef - 1;
        while(l < r) {
            int m = (l + r) / 2;
            for(int i = 0; i < n; i++) {
                M[i] = 0;
            }
            for(int i = l; i <= m; i++) {
                M[tmp[i].se] = 1;
            }
            int ee = Query(M);
            M[hm] = 1;
            int eee = Query(M);
            if(ee == eee) r = m;
            else l = m + 1;
        }
        res.pb(tmp[l].se);
        tmp[l].fi = 1;
    }

    sort(tmp.begin(), tmp.end());
    res.pb(tmp[0].se);

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

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