Submission #546986

#	Time	Username	Problem	Language	Result	Execution time	Memory
546986		ngrace	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	671 ms	972 KiB

dango3

#include "dango3.h"

#include<iostream>
#include <algorithm>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define v vector

namespace {

v<int> ind;
v<int> col;
set<int> found;

}

void Solve(int N, int M) {
  for(int i=1; i<=N*M; i++) ind.push_back(i);

  col=v<int>(N,0);

  for(int b=0; b<M; b++){
    random_device rd;
    mt19937 gen{rd()};
    shuffle(ind.begin(), ind.end(), gen);
    for(int i=0; i<N; i++) col[i]=0;

    if(ind.size()>5*N){
      while(true){
        v<int> ind1;
        for(int i=0; i<4*N; i++){
          ind1.push_back(ind[i]);
        }
        if(Query(ind1)>0) break;

        random_device rd1;
        mt19937 gen1{rd1()};
        shuffle(ind.begin(), ind.end(), gen1);
      }

      int R=4*N;
      for(int i=N; i>0; i--){
        while(R>=0){
          R--;
          v<int> q;
          for(int j=0; j<R; j++) q.push_back(ind[j]);
          for(int j=0; j<N-i; j++) q.push_back(col[j]);
          if(Query(q)==0) break;
        }
        col[N-i]=ind[R];
      }
    }
    else{
      int R=ind.size()-1;
      for(int i=N; i>0; i--){
        int l=i-1, r=R;
        while(l!=r){
          int m=(l+r)/2;
          v<int> q;
          for(int j=0; j<=m; j++) q.push_back(ind[j]);
          for(int j=0; j<N-i; j++) q.push_back(col[j]);
          if(Query(q)>0) r=m;
          else l=m+1;
        }

        col[N-i]=ind[l];
        R=l-1;
      }
    }

    Answer(col);
    for(int it:col) found.insert(it);
    ind.clear();
    for(int i=1; i<=N*M; i++){
      if(found.find(i)==found.end()) ind.push_back(i);
    }
  }
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:30:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     if(ind.size()>5*N){
      |        ~~~~~~~~~~^~~~

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