QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771082 | #7866. Teleportation | gzy | TL | 3ms | 16900kb | C++14 | 1.4kb | 2024-11-22 09:37:36 | 2024-11-22 09:37:36 |
Judging History
answer
#include<bits/stdc++.h>
#define pb emplace_back
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
using ll = long long;
using db = double;
constexpr int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() getchar()//(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? EOF : *p1++)
int rd() {int x = 0, f = 1;char c = gc();while (!isdigit(c)) {if (c == '-') f = -1;c = gc();}while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();return x * f;}
const int N = 2e5 + 7;
int i, j, k, n, m;
int f[N], a[N], v[N], u[N];
set<int> d[N];
queue<int> q, t;
int dis(int x, int y) {return y - x + (x > y) * n;}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
n = rd(), k = rd();
for(i = 0; i < n; i++) v[i] = ((a[i] = rd()) + i) % n;
for(i = 0; i < n; i++) if(i != k) d[v[i]].insert(i);
q.push(k), t.push(k);
for(int x : d[k]) {
if(a[x]) q.push(x), t.push(x);
}
d[k].clear();
while(q.size()) {
k = q.front(), q.pop();
i = t.front(), t.pop();
while(!d[i].size()) {
i = (i - 1 + n) % n;
if(u[i]) break;
}
if(u[i]) continue;
u[k] = 1;
for(int x : d[i]) {
f[x] = f[k] + dis(i, k) + 1;
if(a[x]) q.push(x), t.push(x);
}
q.push(k), t.push(i);
d[i].clear();
}
printf("%d\n", f[0]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 16736kb
input:
4 3 0 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 16900kb
input:
4 3 0 0 0 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 16468kb
input:
4 3 2 2 2 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 3ms
memory: 16872kb
input:
2 1 0 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: -100
Time Limit Exceeded
input:
2 1 1 1