Submission #737806

#	Time	Username	Problem	Language	Result	Execution time	Memory
737806		Deepesson	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	692 ms	596 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]={};
    double soma_bloco_sz=0;
    for(int i=0;i!=M;++i){
        std::vector<int> base;
        int limtemp=1e9;///Vai dar WA no futuro, mt baixo
        int limbase=N;
        int count=0;
        int limita;
        while(base.size()!=N){
            int l=(int)(N-base.size()),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;}
                }
                ++count;
                int ans = Query(concatena(add,base));
                if(ans>=1){
                    r=m;
                    limtemp=r;
                }else {l=m+1;}
            }
            if(base.size()==0){
                soma_bloco_sz+=r;
                limita=r;
            }
            if((N-base.size())*4>r&&i!=M-1){///Utiliza metodo 2
                for(int m=l;m!=-1;--m){
                    std::vector<int> add;
                    int puxa=-1;
                    for(int j=0,cur=0;j<m;++cur){
                        if(!foi[cur]){if(j!=m-1)add.push_back(consulta[cur]);++j;puxa=cur;}
                    }
                    ++count;
                    int ans = Query(concatena(add,base));
                    if(!ans){
                        base.push_back(consulta[puxa]);
                        foi[puxa]=1;
                        --tem;
                        --limtemp;
                    }
                }
                break;
            }
            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;
        }
      //  std::cout<<base.size()<<"!\n";
        //std::cout<<count<<" "<<limita<<"\n";
        Answer(base);
    }
    //std::cout<<(soma_bloco_sz/M)<<"\n";
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:26:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         while(base.size()!=N){
      |               ~~~~~~~~~~~^~~
dango3.cpp:45:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |             if((N-base.size())*4>r&&i!=M-1){///Utiliza metodo 2
      |                ~~~~~~~~~~~~~~~~~^~
dango3.cpp:23:13: warning: unused variable 'limbase' [-Wunused-variable]
   23 |         int limbase=N;
      |             ^~~~~~~
dango3.cpp:25:13: warning: variable 'limita' set but not used [-Wunused-but-set-variable]
   25 |         int limita;
      |             ^~~~~~

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