#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
using namespace std;
typedef long long ll;
#include "gondola.h"
int valid(int n, int inputSeq[])
{
if (n == 1) return true;
vector <int> a(n);
set <int> diff;
bool big = true;
for (int i = 0; i < n; ++i) {
a[i] = inputSeq[i];
big &= (a[i] > n);
diff.insert(a[i]);
}
if ((int)diff.size() != n) return 0;
if (big) return true;
vector <int> nums(n, -1);
for (int i = 0; i < n; ++i) {
if (a[i] <= n) {
nums[i] = a[i] - 1;
}
}
for (int it = 0; it < 2; ++it) {
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) continue;
int j = (i + 1) % n;
if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
if (nums[j] != (nums[i] + 1) % n) {
return false;
}
}
}
return true;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = gondolaSeq[i];
--a[i];
}
vector <int> nums(n, -1);
for (int i = 0; i < n; ++i) {
if (a[i] < n) {
nums[i] = a[i];
}
}
for (int it = 0; it < 2; ++it) {
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) continue;
int j = (i + 1) % n;
if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
if (nums[j] != (nums[i] + 1) % n) {
assert(false);
}
}
}
for (int i = 0; i < n; ++i) if (nums[i] == -1) nums[i] = i;
vector <int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j) {
return a[i] < a[j];
});
int x = n;
int uk = 0;
auto add = [&] (int x) {
replacementSeq[uk++] = x + 1;
};
for (int i : p) {
while (nums[i] != a[i]) {
add(nums[i]);
nums[i] = x++;
}
}
return uk;
}
//----------------------
const int md = 1e9 + 9;
int mul(int a, int b) {
return ((ll)a * b) % md;
}
int power(int a, ll b) {
int res = 1;
while (b > 0) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
vector <int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = inputSeq[i];
--a[i];
}
vector <int> nums(n, -1);
for (int i = 0; i < n; ++i) {
if (a[i] < n) {
nums[i] = a[i];
}
}
for (int it = 0; it < 2; ++it) {
for (int i = 0; i < n; ++i) {
if (nums[i] == -1) continue;
int j = (i + 1) % n;
if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
if (nums[j] != (nums[i] + 1) % n) {
assert(false);
}
}
}
vector <int> intr;
for (int i = 0; i < n; ++i) {
if (a[i] != nums[i]) {
intr.push_back(a[i]);
}
}
sort(intr.begin(), intr.end());
int ans = 1;
int lst = n;
for (int i = 0; i < (int)intr.size(); ++i) {
int cnt = intr[i] - lst;
ans = mul(ans, power((int)intr.size() - i, cnt));
lst = intr[i] + 1;
}
if (nums[0] == -1) {
ans = mul(ans, n);
}
return ans;
}
#ifdef LOCAL
int gondolaSequence[100001];
int replacementSequence[250001];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int i, n, tag;
int nr;
cin >> tag;
cin >> n;
for(i=0;i< n;i++)
cin >> gondolaSequence[i];
switch (tag){
case 1: case 2: case 3:
cout << valid(n, gondolaSequence) << '\n';
break;
case 4: case 5: case 6:
nr = replacement(n, gondolaSequence, replacementSequence);
cout << nr << '\n';
if (nr > 0)
{
for (i=0; i<nr-1; i++)
cout << replacementSequence[i] << " ";
cout << replacementSequence[nr-1] << "\n";
}
else printf("\n");
break;
case 7: case 8: case 9: case 10:
cout << countReplacement(n, gondolaSequence) << '\n';
break;
}
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
13 ms |
2508 KB |
Output is correct |
7 |
Correct |
30 ms |
3964 KB |
Output is correct |
8 |
Correct |
27 ms |
4356 KB |
Output is correct |
9 |
Correct |
8 ms |
1612 KB |
Output is correct |
10 |
Correct |
32 ms |
5196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
13 ms |
2412 KB |
Output is correct |
7 |
Correct |
31 ms |
3916 KB |
Output is correct |
8 |
Correct |
27 ms |
4464 KB |
Output is correct |
9 |
Correct |
9 ms |
1636 KB |
Output is correct |
10 |
Correct |
31 ms |
5060 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
14 ms |
2252 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
38 ms |
5312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
15 ms |
1484 KB |
Output is correct |
12 |
Correct |
18 ms |
1592 KB |
Output is correct |
13 |
Correct |
18 ms |
1100 KB |
Output is correct |
14 |
Correct |
14 ms |
1484 KB |
Output is correct |
15 |
Correct |
23 ms |
2172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
50 ms |
4584 KB |
Output is correct |
10 |
Correct |
36 ms |
3832 KB |
Output is correct |
11 |
Correct |
12 ms |
1484 KB |
Output is correct |
12 |
Correct |
16 ms |
1900 KB |
Output is correct |
13 |
Correct |
3 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
49 ms |
4600 KB |
Output is correct |
10 |
Correct |
42 ms |
3796 KB |
Output is correct |
11 |
Correct |
13 ms |
1584 KB |
Output is correct |
12 |
Correct |
16 ms |
1868 KB |
Output is correct |
13 |
Correct |
5 ms |
592 KB |
Output is correct |
14 |
Correct |
61 ms |
5632 KB |
Output is correct |
15 |
Correct |
79 ms |
6336 KB |
Output is correct |
16 |
Correct |
9 ms |
1428 KB |
Output is correct |
17 |
Correct |
50 ms |
4384 KB |
Output is correct |
18 |
Correct |
27 ms |
2532 KB |
Output is correct |