oj.uz

Submission #546986

# Submission time Handle Problem Language Result Execution time Memory
546986 2022-04-09T05:34:11 Z ngrace Super Dango Maker (JOI22_dango3) C++17
100 / 100
 671 ms 972 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 276 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Correct 8 ms 388 KB Output is correct
5 Correct 9 ms 340 KB Output is correct
6 Correct 9 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 572 KB Output is correct
2 Correct 103 ms 568 KB Output is correct
3 Correct 95 ms 600 KB Output is correct
4 Correct 106 ms 568 KB Output is correct
5 Correct 104 ms 528 KB Output is correct
6 Correct 103 ms 572 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 972 KB Output is correct
2 Correct 671 ms 908 KB Output is correct
3 Correct 526 ms 808 KB Output is correct
4 Correct 534 ms 860 KB Output is correct
5 Correct 568 ms 884 KB Output is correct
6 Correct 572 ms 860 KB Output is correct