QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#289627 | #7859. Bladestorm | ucup-team1516 | WA | 0ms | 3448kb | C++17 | 3.6kb | 2023-12-23 19:59:58 | 2023-12-23 19:59:59 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
inline double time() {
return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}
struct UnionFind {
vector<int> par,num;
vector<int> l;
UnionFind(int n) : par(n), num(n,1), l(n) {
iota(par.begin(), par.end(), 0); //include<numeric>
l = par;
}
int find(int v) {
return (par[v] == v) ? v : (par[v]=find(par[v]));
}
void unite(int u, int v) {
u=find(u), v=find(v);
if (u == v) return;
if (num[u] < num[v]) swap(u, v);
num[u] += num[v];
l[u] = min(l[u], l[v]);
par[v] = u;
}
bool same(int u, int v) {
return find(u) == find(v);
}
int size(int v) {
return num[find(v)];
}
// [l,r]
pair<int,int> kukan(int v) {
v = find(v);
return {l[v], l[v]+num[v]-1};
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q; cin >> q;
while (q--) {
int n,k; cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (k == 1) {
for (int i = 0; i < n; ++i) {
cout << i+1 << " ";
}
cout << "\n";
continue;
}
UnionFind uf(n+k+1);
set<int> st; st.insert(0);
int res = 0;
for (int i = 0; i < n; ++i) {
// for (int j : st) {
// cout << j << " ";
// }
// cout << endl;
// for (int j = 0; j <= n; ++j) {
// cout << uf.kukan(j).first << " ";
// }
// cout << endl;
auto it = st.lower_bound(a[i]);
if (it != st.end() and *it == a[i]) {
cout << res << " ";
continue;
}
if (uf.size(a[i]) != 1) {
cout << res << " ";
continue;
}
it--;
int l = *it; it++;
if (it == st.end()) {
if (a[i]-l <= k) {
st.insert(l+k);
for (int j = 0; j < k-1; ++j) {
uf.unite(l+j, l+j+1);
}
res += 1;
}
else {
res += 1;
st.insert(a[i]);
}
}
else {
st.insert(a[i]);
res += 1;
int r = *it;
if (a[i]-l <= k) {
st.insert(l+k);
for (int j = 0; j < k-1; ++j) {
uf.unite(l+j, l+j+1);
}
a[i] = l+k;
}
if (r-a[i] <= k) {
int len = r-a[i];
for (int j = 0; j < len; ++j) {
uf.unite(a[i]+j, a[i]+j+1);
}
len = k-1-len;
auto p = uf.kukan(a[i]);
for (int j = 0; j < len; ++j) {
uf.unite(p.second+j, p.second+j+1);
}
st.insert(p.second+len+1);
}
}
cout << res << " ";
}
cout << '\n';
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3448kb
input:
3 7 2 4 7 3 6 1 2 5 11 3 10 7 4 9 6 8 5 1 3 2 11 9 2 1 2 3 7 8 9 4 5 6
output:
1 2 3 4 5 5 5 1 2 3 3 3 3 3 4 4 4 4 1 1 2 3 4 4 4 5 5
result:
wrong answer 1st lines differ - expected: '1 2 3 3 4 4 4', found: '1 2 3 4 5 5 5 '