QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#678057 | #7866. Teleportation | absabs | WA | 2ms | 3800kb | C++23 | 2.3kb | 2024-10-26 13:56:39 | 2024-10-26 13:56:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ull unsigned long long
#define ms(x, y) memset(x, y, sizeof x);
#define debug(x) cout << #x << " = " << x << endl;
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define fre \
freopen("input.txt", "r", stdin); \
freopen("output.txt", "w", stdout);
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const double esp = 1e-6;
const ull MOD1 = 1610612741;
const ull MOD2 = 805306457;
const ull BASE1 = 1331;
const ull BASE2 = 131;
#define pre(i, a, b) for (int i = a; i <= b; i++)
#define rep(i, a, b) for (int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()
char *p1, *p2, buf[100000]; // 快读和同步流二者只能选一个
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
int read()
{
int x = 0, f = 1;
char ch = nc();
while (ch < 48 || ch > 57)
{
if (ch == '-')
f = -1;
ch = nc();
}
while (ch >= 48 && ch <= 57)
x = x * 10 + ch - 48, ch = nc();
return x * f;
}
void write(int x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
void solve()
{
int n,x;
cin>>n>>x;
vector<int>v(n+1),dp(n+1,inf);
for(int i=0;i<n;i++){
cin>>v[i];
}
dp[v[0]]=min(dp[v[0]],1ll);
for(int jj=1;jj<=1000;jj++){
for(int i=1;i<n;i++){
dp[(v[0]+i)%n]=min(dp[(v[0]+i)%n],i+1);
}
for(int i=0;i<n;i++){
dp[(i+v[i])%n]=min(dp[(i+v[i])%n],dp[i]+1);
}
}
int ans=dp[x];
for(int i=1;i<=n;i++){
if(i>=x){
ans=min(ans,dp[i]+n-i+x+1);
}else ans=min(ans,dp[i]+x-i);
}
cout<<ans<<endl;
// for(int i=0;i<n;i++)cout<<dp[i]<<" ";
}
// #define LOCAL
signed main()
{
ios
// fre
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto start = std::chrono::high_resolution_clock::now();
#endif
int t = 1;
// cin >> t;
while (t--)
solve();
#ifdef LOCAL
auto end = std::chrono::high_resolution_clock::now();
cout << "Execution time: "
<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
<< " ms" << '\n';
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
4 3 0 1 2 3
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
4 3 0 0 0 0
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
4 3 2 2 2 2
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 1 0 0
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 3568kb
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:
13
result:
wrong answer 1st numbers differ - expected: '10', found: '13'