| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 51732 |
2018-06-20T13:52:03 Z |
Costin Andrei Oncescu(#1294) |
Space Pirate (JOI14_space_pirate) |
C++11 |
|
2000 ms |
1528 KB |
#include<bits/stdc++.h>
using namespace std;
int nr, N, repCyc[3009], lin[3009], col[3009], p[3009], ans[3009];
long long K;
vector < int > cyc[3009];
int aft[3009][3009], d[3009][3009];
bool can[3009][3009];
void init ()
{
for (int i=1; i<=N; i++)
{
int j = p[i], oldJ = i;
can[i][i] = 1, d[i][i] = 0, aft[i][0] = i;
while (can[i][j] == 0)
can[i][j] = 1, d[i][j] = d[i][oldJ] + 1,
aft[i][d[i][j]] = j, oldJ = p[oldJ], j = p[j];
repCyc[i] = j;
if (lin[j] == 0)
{
lin[j] = ++nr, col[j] = 0;
cyc[nr].push_back (j);
int k = p[j];
while (k != j)
col[k] = cyc[nr].size (), lin[k] = nr,
cyc[nr].push_back (k), k = p[k];
}
}
}
int standardJump (int i, long long K)
{
if (lin[i] > 0)
{
int sz = cyc[lin[i]].size (), pos = ((col[i] + K) % sz);
return cyc[lin[i]][pos];
}
int j = repCyc[i], sz = cyc[lin[j]].size (), pos = col[j];
if (K <= d[i][j]) return aft[i][K];
K -= d[i][j], K %= sz, pos = (pos + K) % sz;
return cyc[lin[j]][pos];
}
int brute (int a, int b)
{
int oldP = p[a], curr = 1;
p[a] = b;
long long steps = K;
while (steps --)
curr = p[curr];
p[a] = oldP;
return curr;
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d %lld", &N, &K);
for (int i=1; i<=N; i++)
scanf ("%d", &p[i]);
init ();
int standardEnd = standardJump (1, K);
for (int a=1; a<=N; a++)
for (int b=1; b<=N; b++)
{
int curr = -1;
if (!can[1][a]) curr = standardEnd;
else
if (!can[1][b])
{
if (can[b][1])
{
int sz = d[b][1] + 1 + d[1][a], k = (K % sz);
if (k <= d[1][a]) curr = aft[1][k];
else curr = aft[b][k - 1 - d[1][a]];
}
else
curr = standardJump (b, K - d[1][a] - 1);
}
else
if (d[1][a] >= d[1][b])
{
int sz = d[1][a] - d[1][b] + 1, k = ((K - d[1][b]) % sz);
curr = standardJump (b, k);
}
else
if (lin[a] == 0)
curr = standardJump (b, K - d[1][a] - 1);
else
{
assert (lin[b] == lin[a]);
if (lin[1] == 0)
{
int j = repCyc[1], sz = ((int) cyc[lin[a]].size ()) - (d[1][b] - d[1][a] - 1), k = (K - d[1][j]) % sz;
if (k <= d[j][a]) curr = standardJump (j, k);
else curr = standardJump (b, k - d[j][a] - 1);
}
else
{
int sz = ((int) cyc[lin[a]].size ()) - (d[1][b] - d[1][a] - 1), k = (K % sz);
if (k <= d[1][a]) curr = standardJump (1, k);
else curr = standardJump (b, k - d[1][a] - 1);
}
}
curr = brute (a, b);
/* printf ("%d%c", curr, " \n"[b == N]);
if (curr != brute (a, b))
{
printf ("WA (%d %d) %d instead of %d\n", a, b, curr, brute (a, b));
return 0;
}*/
ans[curr] ++;
}
for (int i=1; i<=N; i++)
printf ("%d\n", ans[i]);
return 0;
}
Compilation message
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %lld", &N, &K);
~~~~~~^~~~~~~~~~~~~~~~~~~
space_pirate.cpp:64:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &p[i]);
~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
1528 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
1528 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5 ms |
1528 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2078 ms |
1528 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
