Submission #441328

#	Time	Username	Problem	Language	Result	Execution time	Memory
441328		Agnimandur	Library (JOI18_library)	C++17	0 / 100	1 ms	200 KiB

library

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

#define sz(x) ((int) (x).size())
#define vi vector<int>
#define add push_back
using namespace std;

vi build(vi &alive, int L, int R) {
    int N = sz(alive);
    vi ret;
    ret.assign(N,0);
    int ind = 0;

    for (int i = 0; i < N; i++) {
        if (alive[i]==1 && (L <= ind && ind <= R)) {
            ret[i] = 1;
            ind++;
        }
    }
    return ret;
}

int search(vi &alive, int L) {
    int N = sz(alive);
    int ind = 0;
    for (int i = 0; i < N; i++) {
        if (alive[i]==1) {
            if (ind==L) return i;
            ind++;
        }
    }
    return -1;
}

void Solve(int N) {
    int end = -1;
    for (int i = 0; i < N; i++) {
        vi nums;
        nums.assign(N,1);
        nums[i] = 0;
        int A = Query(nums);
        if (A==1) {
            end = i;
            break;
        }
    }

    vi ans;
    ans.add(end);

    vi alive;
    alive.assign(N,1);
    alive[end] = 0;

    for (int s = N-1; s >= 1; s--) {
        int lo = 0;
        int hi = s-1;
        int last = ans[sz(ans)-1];

        while (lo < hi) {
            int m = (lo+hi)/2;
            vi M = build(alive,lo,m);
            int x = 1;
            if (lo<m) x = Query(M);
            M[last] = 1;
            int y = Query(M);
            if (y==x) {
                hi = m;
            } else {
                lo = m+1;
            }
        }
        int index = search(alive,lo);
        ans.add(index);
        alive[index] = 0;
    }

    for (int i = 0; i < N; i++) {
        ans[i]++;
    }
	Answer(ans);
}

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