oj.uz

Submission #620206

# Submission time Handle Problem Language Result Execution time Memory
620206 2022-08-03T03:41:34 Z czhang2718 Super Dango Maker (JOI22_dango3) C++17
22 / 100
 1854 ms 628 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a; i<=b; i++)

int qry(vector<int> v){
  cout << "? ";
  for(int x:v) cout << x << " ";
  cout << endl;
int ret; cin >> ret;
return ret;
}

void ans(vector<int> v){
  cout << "! ";
  for(int x:v) cout << x << " ";
    cout << endl;
}
vector<vector<int>> dango;
bool ki[100000];
vector<int> idx;

void solve(int l, int r, int li, int ri){
  if(r<l) return;
  int m=(l+r)/2;
  int p=li-1;
  auto ck=[&](int p)->bool{
    // cout << "try " << p << endl;
    vector<int> qu;
    for(int i=0; i<=p; i++){
      qu.push_back(idx[i]);
    }
    for(int i=0; i<m; i++){
      for(int x:dango[i]) qu.push_back(x);
    }
    for(int &x:qu) x++;
    return Query(qu)<m;
  };
  for(int k=31-__builtin_clz(ri-li+1); k>=0; k--){
    if(p+(1<<k)<ri && ck(p+(1<<k))) p+=(1<<k);
  }
  p++;
  ki[p]=1;
  // cout << "ki " << p << " = " << it << endl;
  solve(l, m-1, li, p-1);
  solve(m+1, r, p, ri);
}

void Solve(int n, int m) {
  dango.resize(m);
  idx.resize(n*m);
  iota(idx.begin(), idx.end(), 0);

  for(int it=1; it<=n; it++){
    int N=idx.size();
    solve(1, m, 0, N-1);
    int j=0;
    vector<int> idx2;
    for(int i=0; i<N; i++){
      if(ki[i]){
        dango[j++].push_back(idx[i]);
      }
      else idx2.push_back(idx[i]);
      ki[i]=0;
    }
    swap(idx, idx2);
  }

  for(int i=0; i<m; i++){
    for(int &x:dango[i]) x++;
    Answer(dango[i]);
  }
}

// int main(){
//   Solve(3, 2);
// }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 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 31 ms 380 KB Output is correct
2 Correct 30 ms 340 KB Output is correct
3 Correct 18 ms 380 KB Output is correct
4 Correct 18 ms 340 KB Output is correct
5 Correct 29 ms 376 KB Output is correct
6 Correct 29 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 604 KB Output is correct
2 Correct 764 ms 588 KB Output is correct
3 Correct 361 ms 500 KB Output is correct
4 Correct 378 ms 624 KB Output is correct
5 Correct 751 ms 488 KB Output is correct
6 Correct 728 ms 484 KB Output is correct

Subtask #4
0 / 78.0

# Verdict Execution time Memory Grader output
1 Incorrect 1854 ms 628 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -