QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#289627#7859. Bladestormucup-team1516WA 0ms3448kbC++173.6kb2023-12-23 19:59:582023-12-23 19:59:59

Judging History

你现在查看的是最新测评结果

  • [2023-12-23 19:59:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3448kb
  • [2023-12-23 19:59:58]
  • 提交

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 '