| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 620198 | czhang2718 | Super Dango Maker (JOI22_dango3) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
int kill[100000];
int it;
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++){
// cout << "kill[" << i << "] " << kill[i] << "\n";
if(kill[i] && kill[i]<it) continue;
qu.push_back(i);
}
for(int i=0; i<m; i++){
for(int x:dango[i]) qu.push_back(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++;
kill[p]=it;
// cout << "kill " << 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);
for(it=1; it<=n; it++){
solve(1, m, 0, n*m-1);
int j=0;
for(int i=0; i<n*m; i++){
if(kill[i]==it){
dango[j++].push_back(i+1);
}
}
}
for(int i=0; i<m; i++) Answer(dango[i]);
}
// int main(){
// Solve(3, 2);
// }