제출 #1142186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142186		denislav	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	282 ms	636 KiB

dango3

#include "dango3.h"
//#include "grader.cpp"
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

const int MAX=1e6+11;
bool vis[MAX];

mt19937 rng(69);

void Solve(int N, int M)
{
    int n=N,m=M;
    for(int t=1;t<=m;t++)
    {
        vector<int> v,ans;
        for(int i=1;i<=n*m;i++) if(!vis[i]) v.push_back(i);

        shuffle(v.begin(),v.end(),rng);

        int cnt=m-t;
        while(true)
        {
            int bk=v.back();
            v.pop_back();

            int resp=Query(v);
            if(resp==cnt)
            {
                vis[bk]=1;
                ans.push_back(bk);
                if((int)ans.size()==n)
                {
                    Answer(ans);
                    break;
                }
            }
            else v.insert(v.begin(),bk);
        }
    }
}

/*
3 2
3 3 1 2 1 2
*/


/*
4 4
2 2 3 2 4 4 3 2 3 1 1 3 4 1 4 1
*/

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