Submission #737786

#	Time	Username	Problem	Language	Result	Execution time	Memory
737786		Deepesson	Super Dango Maker (JOI22_dango3)	C++17	0 / 100	13 ms	536 KiB

dango3

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

void Answer(const std::vector<int> &a);
int Query(const std::vector<int> &x);

std::vector<int> concatena(std::vector<int> a,std::vector<int> b){
    for(auto&x:b)a.push_back(x);
    return a;
}
void Solve(int N, int M) {
    int tot = N*M;
    std::vector<int> consulta;
    for(int i=0;i!=tot;++i)consulta.push_back(i+1);
    std::random_shuffle(consulta.begin(),consulta.end());
    int tem=tot;
    bool foi[tot]={};
    for(int i=0;i!=M;++i){
        std::vector<int> base;
        int limtemp=1e9;
        int limbase=N;
        while(base.size()!=N){
            int l=limbase,r=std::min(limtemp,tem);
            while(l<r){
                int m = (l+r)/2;
                std::vector<int> add;
                for(int j=0,cur=0;j<m;++cur){
                    if(!foi[cur]){add.push_back(consulta[cur]);++j;}
                }
                if(Query(concatena(add,base))>=1){
                    r=m;
                    limtemp=r;
                }else {l=m+1;limbase=m;}
            }
            int puxa=-1;
            for(int j=0,cur=0;j<l;++cur){
                if(!foi[cur]){++j;puxa=cur;}
            }
            base.push_back(consulta[puxa]);
            foi[puxa]=1;
            --tem;
            --limbase;
        }
        Answer(base);
    }
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:22:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         while(base.size()!=N){
      |               ~~~~~~~~~~~^~~

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