/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000009ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
#ifndef death
#include "gondola.h"
#endif
int valid(int n, int inputSeq[])
{
vector<int> a, b;
for (int i = 0; i < n; i++)
a.PB(inputSeq[i]);
b = a;
for (int i = 0; i < n; i++)
{
if (a[i] > n)
continue;
for (int j = 0; j < n; j++)
b[(a[i] - 1 + j) % n] = a[(i + j) % n];
break;
}
a = b;
map<int, int> used;
for (int i = 0; i < n; i++)
{
if ((a[i] <= n && i + 1 != a[i]) || used[a[i]])
return 0;
used[a[i]] = 1;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<int> ans;
vector<pair<int, int>> nxt;
vector<int> a, b;
for (int i = 0; i < n; i++)
a.PB(gondolaSeq[i]);
assert(valid(n, gondolaSeq));
b = a;
for (int i = 0; i < n; i++)
{
if (a[i] > n)
continue;
for (int j = 0; j < n; j++)
b[(a[i] - 1 + j) % n] = a[(i + j) % n];
break;
}
a = b;
for (int i = 0; i < n; i++)
if (a[i] > n)
nxt.PB(MP(a[i], i));
sort(all(nxt));
while (!nxt.empty())
{
int pos = nxt.back().second;
nxt.pop_back();
int mn = n;
if (!nxt.empty())
mn = nxt.back().first;
for (int i = a[pos]; i > mn; i--)
ans.PB(pos);
}
reverse(all(ans));
for (int i = 0; i < ans.size(); i++)
replacementSeq[i] = (ans[i] + i) % n + 1;
return ans.size();
}
int countReplacement(int n, int inputSeq[])
{
return 0;
}
#ifdef death
int main()
{
int N, A[10002], B[10002];
cin >> N;
for (int i = 0; i < N; i++)
cin >> A[i];
N = replacement(N, A, B);
cout << endl;
for (int i = 0; i < N; i++)
cout << B[i] << " ";
cout << endl;
return 0;
}
#endif
/*
7
5 6 7 1 2 3 4
7
5 6 7 1 2 10 4
5
2 6 15 9 1
*/
Compilation message
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++)
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
22 ms |
2676 KB |
Output is correct |
7 |
Correct |
16 ms |
1520 KB |
Output is correct |
8 |
Correct |
45 ms |
4460 KB |
Output is correct |
9 |
Correct |
12 ms |
1660 KB |
Output is correct |
10 |
Correct |
52 ms |
5232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
22 ms |
2552 KB |
Output is correct |
7 |
Correct |
16 ms |
1520 KB |
Output is correct |
8 |
Correct |
44 ms |
4596 KB |
Output is correct |
9 |
Correct |
13 ms |
1656 KB |
Output is correct |
10 |
Correct |
52 ms |
5360 KB |
Output is correct |
11 |
Correct |
2 ms |
256 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
9 ms |
888 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
17 ms |
1520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
312 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |