Submission #737797

#	Time	Username	Problem	Language	Result	Execution time	Memory
737797		Deepesson	Super Dango Maker (JOI22_dango3)	C++17	22 / 100	595 ms	528 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;
    srand(time(0));
    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=(int)(N-base.size()),r=std::min({4000,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;}
                }
                int ans = Query(concatena(add,base));
                if(ans>=1){
                    r=m;
                    limtemp=r;
                }else {l=m+1;}
            }
            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;
            --limtemp;
        }
        Answer(base);
    }
}

Compilation message (stderr)

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

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