QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#142370 | #1375. TripTik | Anwar_Gehad_Maghraby# | WA | 10ms | 73864kb | C++23 | 2.3kb | 2023-08-19 00:38:35 | 2023-08-19 00:38:38 |
Judging History
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'