QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288722 | #7866. Teleportation | ucup-team1469# | WA | 1ms | 3516kb | C++17 | 4.3kb | 2023-12-23 13:13:14 | 2023-12-23 13:13:14 |
Judging History
answer
#ifndef LOCAL
#define FAST_IO
#endif
// ============
#include <bits/stdc++.h>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32)(x.size())
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
using pi = pair<i32, i32>;
using pl = pair<i64, i64>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;
template <typename T>
using VVVV = V<V<V<V<T>>>>;
template <typename T>
using PQR = priority_queue<T, V<T>, greater<T>>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
template <typename T>
i32 lob(const V<T> &arr, const T &v) {
return (i32)(lower_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
i32 upb(const V<T> &arr, const T &v) {
return (i32)(upper_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
V<i32> argsort(const V<T> &arr) {
V<i32> ret;
iota(ALL(ret), 0);
sort(ALL(ret), [&](i32 i, i32 j) -> bool {
if (arr[i] == arr[j]) {
return i < j;
} else {
return arr[i] < arr[j];
}
});
return ret;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
istream &operator>>(istream &is, i128 &x) {
i64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, i128 x) {
os << (i64)x;
return os;
}
istream &operator>>(istream &is, u128 &x) {
u64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, u128 x) {
os << (u64)x;
return os;
}
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
SetUpIO() {
#ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cout << fixed << setprecision(15);
}
} set_up_io;
void scan(char &x) { cin >> x; }
void scan(u32 &x) { cin >> x; }
void scan(u64 &x) { cin >> x; }
void scan(i32 &x) { cin >> x; }
void scan(i64 &x) { cin >> x; }
void scan(string &x) { cin >> x; }
template <typename T>
void scan(V<T> &x) {
for (T &ele : x) {
scan(ele);
}
}
void read() {}
template <typename Head, typename... Tail>
void read(Head &head, Tail &...tail) {
scan(head);
read(tail...);
}
#define CHAR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define U32(...) u32 __VA_ARGS__; read(__VA_ARGS__);
#define U64(...) u64 __VA_ARGS__; read(__VA_ARGS__);
#define I32(...) i32 __VA_ARGS__; read(__VA_ARGS__);
#define I64(...) i64 __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define VEC(type, name, size) V<type> name(size); read(name);
#define VVEC(type, name, size1, size2) VV<type> name(size1, V<type>(size2)); read(name);
// ============
#ifdef DEBUGF
#else
#define DBG(x) (void) 0
#endif
void solve() {
I32(n, k);
VEC(i32, a, n);
V<i32> dist(n, INF);
PQR<pair<i32, i32>> que;
dist[0] = 0;
que.emplace(0, 0);
while (!que.empty()) {
auto [d, v] = que.top();
que.pop();
if (d > dist[v]) {
continue;
}
if (v != 0 && chmin(dist[(v + 1) % n], dist[v] + 1)) {
que.emplace(dist[v] + 1, (v + 1) % n);
}
if (chmin(dist[(v + a[v]) % n], dist[v] + 1)) {
que.emplace(dist[v] + 1, (v + 1) % n);
}
if (chmin(dist[(v + a[v] + 1) % n], dist[v] + 2)) {
que.emplace(dist[v] + 2, (v + 1) % n);
}
}
cout << dist[k] << '\n';
}
int main() {
i32 t = 1;
//cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3428kb
input:
4 3 0 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
4 3 0 0 0 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
4 3 2 2 2 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
2 1 0 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
2 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3516kb
input:
300 25 182 9 13 211 258 132 27 42 218 200 271 258 164 121 8 84 29 195 141 290 110 0 272 93 142 134 140 32 232 99 162 199 297 287 212 29 182 53 61 98 116 282 75 245 230 165 22 4 179 89 274 231 46 299 248 208 200 285 221 50 221 199 294 241 195 138 22 204 113 100 132 276 158 146 238 178 100 94 131 157 ...
output:
1000000100
result:
wrong answer 1st numbers differ - expected: '10', found: '1000000100'