| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 886374 | dong_liu | Super Dango Maker (JOI22_dango3) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;
/*
int s(int n) {
return n/4000;
}
int calc(int l, int r) {
if (s(r) == s(l-1)) return 1;
if (l == r) return 1;
int m = (l+r)/2;
return 1+calc(l,m)+calc(m+1,r);
}
*/
#ifdef LOCAL
int n, m, a[int(1e4)+1];
int Query(vector<int> v) {
vector<int> c(n);
for (int i : v) c[a[i]-1]++;
// for (int i : v) cout << i << ' ';
// cout << "| GOT " << *min_element(begin(c),end(c)) << endl;
return *min_element(begin(c),end(c));
}
void Answer(vector<int> v) {
for (int x : v) cout << x << ' ';
cout << '\n';
}
#endif
void Solve(int n, int m) {
vector<int> on(n*m+1);
for (int i = 1; i <= n*m - (m-1); i++)
on[i] = 1;
auto get_v = [&]() {
vector<int> v;
for (int i = 1; i <= n*m; i++) if (on[i]) v.push_back(i);
return v;
};
int c = n*m - (m-1);
for (int i = 1; i <= n*m; i++)
if (on[i]) {
on[i] = 0;
if (Query(get_v())) {
c--;
if (c == n) break;
} else {
on[i] = 1;
}
}
auto base = get_v();
vector<int> a(n*m+1);
int id = 0;
for (int i : base) a[i] = ++id;
for (int i : base) {
vector<int> p;
for (int j = 1; j <= n*m; j++) if (!a[j]) p.push_back(j);
queue<pii> q;
q.push({0, sz(p)-1});
while (sz(q)) {
auto [l,r] = q.front(); q.pop();
auto v = base;
v.erase(find(begin(v), end(v), i));
for (int j = l; j <= r; j++) v.push_back(p[j]);
if (Query(v)) {
if (l == r) a[p[l]] = a[i];
else {
int m = (l+r)/2;
q.push({l,m}), q.push({m+1,r});
}
}
}
}
vector<vector<int>> at(n+1);
for (int i = 1; i <= n*m; i++) {
assert(a[i]);
at[a[i]].push_back(i);
// cout << a[i] << ' ';
}
// cout << '\n';
// return;
for (int it = 0; it < m; it++) {
vector<int> v;
for (int i = 1; i <= n; i++) {
assert(sz(at[i]));
v.push_back(at[i].back());
at[i].pop_back();
}
Answer(v);
}
}
#ifdef LOCAL
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n*m; i++) cin >> a[i];
Solve(n, m);
}
#endif