# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
292855 | AaronNaidu | Gondola (IOI14_gondola) | C++14 | 23 ms | 2808 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
const ll mod = 1000000009;
int maxAns;
bool done[300000];
bool used[300000];
int replacedBy[300000];
int valid(int n, int inputSeq[]) {
int minIndex = -1;
int minAns = 1000000000;
int maxIndex = -1;
maxAns = 0;
int outOfRange = 0;
for (int i = 0; i < n; i++)
{
if (done[inputSeq[i]])
{
return 0;
}
done[inputSeq[i]] = true;
if (inputSeq[i] < minAns)
{
minIndex = i;
minAns = inputSeq[i];
}
if (inputSeq[i] > maxAns)
{
maxIndex = i;
maxAns = inputSeq[i];
}
if (inputSeq[i] > n)
{
outOfRange++;
}
}
if (minAns > n)
{
return 1;
}
if (n + outOfRange > maxAns)
{
return 0;
}
for (int i = 0; i < n; i++)
{
if (inputSeq[i] <= n)
{
int diff = i - minIndex;
if (diff <= 0)
{
diff += n;
}
int expectedAns = minAns + diff;
if (expectedAns <= 0)
{
expectedAns += n;
}
if (expectedAns%n != inputSeq[i]%n)
{
return 0;
}
}
}
return 1;
}
int replacement(int n, int inputSeq[], int replacementSeq[]) {
int minIndex = -1;
int minAns = 1000000000;
int maxIndex = -1;
int maxAns = 0;
int outOfRange = 0;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] < minAns)
{
minIndex = i;
minAns = inputSeq[i];
}
if (inputSeq[i] > maxAns)
{
maxIndex = i;
maxAns = inputSeq[i];
}
if (inputSeq[i] > n)
{
outOfRange++;
}
used[inputSeq[i]] = true;
}
if (minAns <= n)
{
for (int i = 0; i < n; i++)
{
if (inputSeq[i] > n)
{
int diff = i - minIndex;
if (diff <= 0)
{
diff += n;
}
int expectedAns = minAns + diff;
if (expectedAns > n)
{
expectedAns -= n;
}
if (expectedAns <= 0)
{
expectedAns += n;
}
replacedBy[inputSeq[i]] = expectedAns;
}
}
int currPointer = n;
int newPointer = n;
int l = 0;
while (currPointer < maxAns)
{
if (replacedBy[newPointer])
{
replacementSeq[l] = replacedBy[newPointer];
l++;
for (int j = currPointer+1; j < newPointer; j++)
{
replacementSeq[l] = j;
l++;
}
currPointer = newPointer;
}
newPointer++;
}
return l;
}
vector<pair<int, int> > v;
for (int i = 0; i < n; i++)
{
v.push_back({inputSeq[i], i});
}
sort(v.begin(), v.end());
int pointer1 = n + 1;
int l = 0;
for (int i = 0; i < n; i++)
{
replacementSeq[l] = v[i].second + 1;
l++;
for (int j = pointer1; j < v[i].first; j++)
{
replacementSeq[l] = j;
l++;
}
pointer1 = v[i].first + 1;
}
return l;
}
int finish(int n, int inputSeq[]) {
vector<int> v;
int s = 0;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] > n)
{
s++;
v.push_back(inputSeq[i]);
}
}
sort(v.rbegin(), v.rend());
int pointer1 = n + 1;
ll finAns = 1;
while (v.size())
{
//cout << "pointer is " << pointer1 << "\n";
if (v[v.size()-1] == pointer1)
{
v.pop_back();
pointer1++;
}
else
{
finAns *= v.size();
finAns %= mod;
pointer1++;
}
}
return finAns;
}
int countReplacement(int n, int inputSeq[]) {
int minIndex = -1;
int minAns = 1000000000;
int maxIndex = -1;
maxAns = 0;
int outOfRange = 0;
for (int i = 0; i < n; i++)
{
if (done[inputSeq[i]])
{
return 0;
}
done[inputSeq[i]] = true;
if (inputSeq[i] < minAns)
{
minIndex = i;
minAns = inputSeq[i];
}
if (inputSeq[i] > maxAns)
{
maxIndex = i;
maxAns = inputSeq[i];
}
if (inputSeq[i] > n)
{
outOfRange++;
}
}
if (minAns > n)
{
ll nearAns = finish(n, inputSeq);
nearAns *= n;
nearAns %= mod;
return nearAns;
}
if (n + outOfRange > maxAns)
{
return 0;
}
for (int i = 0; i < n; i++)
{
if (inputSeq[i] <= n)
{
int diff = i - minIndex;
if (diff <= 0)
{
diff += n;
}
int expectedAns = minAns + diff;
if (expectedAns <= 0)
{
expectedAns += n;
}
if (expectedAns%n != inputSeq[i]%n)
{
return 0;
}
}
}
return finish(n, inputSeq);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |