제출 #1319599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319599		Ghulam_Junaid	Super Dango Maker (JOI22_dango3)	C++20	22 / 100	199 ms	708 KiB

dango3

#include <bits/stdc++.h>
#include "dango3.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 400 * 25 + 100;
bool dead[N], on[N];
int n;

int qdec(deque<int> &dq){
    vector<int> vec;
    for (int x : dq)
        vec.push_back(x);
    return Query(vec);
}

void work(vector<int> cur){
    deque<int> dq;
    for (int x : cur)
        dq.push_back(x);
    while (dq.size() > n){
        int f = dq.front();
        dq.pop_front();
        if (qdec(dq) == 0)
            dq.push_back(f);
    }
    vector<int> perm;
    for (int x : dq)
        perm.push_back(x), dead[x] = 1;
    Answer(perm);
}

void Solve(int nn, int m){
    n = nn;
    vector<int> vec;
    for (int i = 1; i <= n * m; i ++)
        vec.push_back(i);

    while (vec.size()){
        if (vec.size() == n){ 
            Answer(vec);
            break;
        }
        
        shuffle(vec.begin(), vec.end(), rng);
        vector<int> cur = vec;
        int lo = n - 1, hi = vec.size();
        while (hi - lo > 1){
            int mid = (lo + hi) / 2;
            vector<int> qq;
            for (int i = 0; i < mid; i ++)
                qq.push_back(vec[i]);

            int val = Query(qq);
            if (val == 0)
                lo = mid;
            else if (val == 1){
                cur = qq;
                break;
            }
            else{
                cur = qq;
                hi = mid;
            }
        }
        work(cur);

        vector<int> tmp;
        for (int i : vec)
            if (!dead[i])
                tmp.push_back(i);
        vec = tmp;
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 78