# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
337057 |
2020-12-18T04:35:18 Z |
blue |
Gondola (IOI14_gondola) |
C++11 |
|
77 ms |
5996 KB |
#include "gondola.h"
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int valid(int n, int inputSeq[])
{
set<int> S;
int prev = -1, prev_pos = -1;
for(int i = 0; i < n; i++)
{
if(S.find(inputSeq[i]) != S.end()) return 0;
S.insert(inputSeq[i]);
if(inputSeq[i] > n) continue;
if(prev != -1)
{
if((i - prev_pos + n) % n != (inputSeq[i] - prev + n) % n) return 0;
}
prev = inputSeq[i];
prev_pos = i;
}
return 1;
}
int* gondolaSeqGlobal;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
gondolaSeqGlobal = gondolaSeq;
vector<int> I(n);
for(int i = 0; i < n; i++) I[i] = i;
sort(I.begin(), I.end(), [] (int x, int y)
{
return gondolaSeqGlobal[x] < gondolaSeqGlobal[y];
});
int pos1 = 0;
for(int i = 0; i < n; i++)
{
if(gondolaSeq[i] <= n)
{
pos1 = (i + 1 - gondolaSeq[i] + n) % n;
break;
}
}
int l = 0;
if(gondolaSeq[ I[0] ] > n)
{
replacementSeq[l] = ((I[0] - pos1 + n) % n) + 1;
l++;
}
for(int j = n+1; j < gondolaSeq[ I[0] ]; j++)
{
replacementSeq[l] = j;
l++;
}
for(int i = 1; i < n; i++)
{
if(gondolaSeq[ I[i] ] > n)
{
replacementSeq[l] = ((I[i] - pos1 + n) % n) + 1;
l++;
}
for(int j = max(n+1, gondolaSeq[ I[i-1] ] + 1); j < gondolaSeq[ I[i] ]; j++)
{
replacementSeq[l] = j;
l++;
}
}
return l;
}
long long mod = 1e9 + 9;
long long pow(long long b, long long p)
{
if(p == 0) return 1;
if(p % 2) return (b * pow(b, p-1)) % mod;
long long temp = pow(b, p/2);
return (temp * temp) % mod;
}
long long ll(int x)
{
return (long long)(x);
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
int original = 0;
for(int i = 0; i < n; i++) if(inputSeq[i] <= n) original = 1;
sort(inputSeq, inputSeq + n);
int x;
for(x = 0; x < n && inputSeq[x] <= n; x++);
//Either x >= n or inputSeq[x] > n
if(x >= n) return 1;
long long res = pow(n-x, inputSeq[x] - n - 1);
for(x++; x < n; x++)
{
res = (res * pow(ll(n-x), ll(inputSeq[x] - inputSeq[x-1] - 1))) % mod;
}
if(!original)
{
res = (res * n) % mod;
}
return int(res);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
14 ms |
2284 KB |
Output is correct |
7 |
Correct |
11 ms |
620 KB |
Output is correct |
8 |
Correct |
30 ms |
3948 KB |
Output is correct |
9 |
Correct |
8 ms |
1516 KB |
Output is correct |
10 |
Correct |
38 ms |
4588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
14 ms |
2284 KB |
Output is correct |
7 |
Correct |
11 ms |
620 KB |
Output is correct |
8 |
Correct |
32 ms |
3948 KB |
Output is correct |
9 |
Correct |
8 ms |
1516 KB |
Output is correct |
10 |
Correct |
34 ms |
4588 KB |
Output is correct |
11 |
Correct |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
5 ms |
492 KB |
Output is correct |
14 |
Correct |
0 ms |
364 KB |
Output is correct |
15 |
Correct |
11 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
13 ms |
876 KB |
Output is correct |
12 |
Correct |
16 ms |
1004 KB |
Output is correct |
13 |
Correct |
17 ms |
1124 KB |
Output is correct |
14 |
Correct |
12 ms |
876 KB |
Output is correct |
15 |
Correct |
25 ms |
2156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
51 ms |
4076 KB |
Output is correct |
10 |
Correct |
38 ms |
3436 KB |
Output is correct |
11 |
Correct |
14 ms |
1516 KB |
Output is correct |
12 |
Correct |
17 ms |
1772 KB |
Output is correct |
13 |
Correct |
4 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
0 ms |
364 KB |
Output is correct |
9 |
Correct |
48 ms |
4076 KB |
Output is correct |
10 |
Correct |
38 ms |
3436 KB |
Output is correct |
11 |
Correct |
14 ms |
1516 KB |
Output is correct |
12 |
Correct |
17 ms |
1772 KB |
Output is correct |
13 |
Correct |
4 ms |
620 KB |
Output is correct |
14 |
Correct |
61 ms |
5500 KB |
Output is correct |
15 |
Correct |
77 ms |
5996 KB |
Output is correct |
16 |
Correct |
12 ms |
1388 KB |
Output is correct |
17 |
Correct |
45 ms |
4204 KB |
Output is correct |
18 |
Correct |
27 ms |
2540 KB |
Output is correct |