QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142370#1375. TripTikAnwar_Gehad_Maghraby#WA 10ms73864kbC++232.3kb2023-08-19 00:38:352023-08-19 00:38:38

Judging History

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

  • [2023-08-19 00:38:38]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:73864kb
  • [2023-08-19 00:38:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10, OO = 1e9;
vector<pair<int,int>> to[30][N];

int main() {
    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);

    int n, k;
    cin>>n>>k;
    int x[n + 1], I[n + 1];
    for(int i = 1; i <= n; i++){
        I[i]= i;
        cin>>x[i];
    }
    I[0]= x[0]= 0;

    sort(I, I + n + 1, [&](int i, int j){
        return x[i] < x[j];
    });
    int width= 1;
    for(int w = 0; w < 30; w++)
    {
        set<pair<int,int>> st;
        int L= 0, R= 0;
        for(int i = 0; i <= n; i++){
            while(R + 1 <= n && (x[I[R + 1]] - x[I[i]]) * 2 <= width){
                st.insert({I[R + 1], x[I[R + 1]]});
                ++R;
            }
            while((x[I[i]] - x[I[L]]) * 2 > width){
                st.erase({I[L], x[I[L]]});
                ++L;
            }
            vector<int> out;
            for(int j = 0; j < k; j++){
                if((int)(st.size())){
                    auto it = *st.rbegin();
                    out.push_back(it.first);
                    st.erase(it);
                    to[w][I[i]].push_back({w, it.first});
                }
            }
            for(int j : out) st.insert({j, x[j]});
        }
        width *= 2;
    }
    
    for(int w = 0; w + 1 < 30; w++){
        for(int i = 0; i <= n; i++){
            to[w][i].push_back({w + 1, i});
            to[w + 1][i].push_back({w, i});
        }
    }

    vector<vector<int>> d(30, vector<int>(n + 1, OO));
    queue<pair<int, int>> Q;
    d[1][0] = 0, Q.emplace(1, 0);

    while (!Q.empty()) {
        int w = Q.front().first;
        int v = Q.front().second;
        Q.pop();
        for (auto [w_, u] : to[w][v]) {
            if (d[w_][u] > d[w][v] + 1) {
                d[w_][u] = d[w][v] + 1;
                Q.emplace(w_, u);
            }
        }
    }
    vector<int> ans(n + 1, OO);
    for (int i = 1; i <= n; ++i) {
        ans[i] = d[0][i];
        for (int w = 0; w < 30; ++w) {
            set<int> st;
            for (auto [_, x] : to[w][i]) {
                if (x == i && _ == w) {
                    ans[i] = min(ans[i], d[w][i]);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << (ans[i] == OO ? -1 : ans[i]) << "\n";
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 10ms
memory: 73864kb

input:

4 2
-2
-1
-3
2

output:

2
1
-1
2

result:

wrong answer 1st lines differ - expected: '3', found: '2'