| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 586228 | LastRonin | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 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 "gondola.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;
int valid(int n, int inputSeq[]) {
int pos = -1;
set<ll> b;
for(int i = 0; i < n; i++)
b.insert(inputSeq[i]);
if(b.size() != n)return 0;
for(int i = 0; i < n; i++) {
if(inputSeq[i] <= n) {
pos = i;
break;
}
}
if(pos == -1)return 1;
ll a = inputSeq[pos];
ll nxt = pos;
for(int j = 0; j <= n; j++) {
if(inputSeq[nxt] <= n && inputSeq[nxt] != a)return 0;
a++;
if(a == n + 1)a = 1;
nxt = (nxt + 1) % n;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector<pair<int, int>> z;
int pos = -1;
int a[n] = {0};
for(int i = 0; i < n; i++) {
if(gondolaSeq[i] <= n) {
pos = i;
}
z.pb(mp(gondolaSeq[i], i));
}
int b = (pos == -1 ? 1 : gondolaSeq[pos]);
pos = (pos == -1 ? 0 : pos);
for(int j = 0 ; j < n; j++) {
a[pos] = b;
pos = (pos + 1) % n;
b++;
if(b == n + 1)b = 1;
}
int cur = 0;
ll mx = n;
sort(z.begin(), z.end());
for(auto u : z) {
if(u.f <= n)continue;
replacementSeq[cur++] = a[u.s];
mx++;
while(mx != u.f) {
replacementSeq[cur++] = mx;
mx++;
}
}
return cur;
}
const ll mod = 1e9 + 9;
ll bp(ll a, ll b) {
ll c = 1ll;
while(b) {
if(b&1)
c = c * a % mod;
b >>= 1ll;
a = a * a % mod;
}
return c;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq))return 0;
int cnt = 0;
int pos = -1;
vector<pair<int, int>> z;
for(int i = 0; i < n; i++) {
cnt += (inputSeq[i] <= n);
if(inputSeq[i] > n)
z.pb(mp(inputSeq[i], i));
}
if(cnt == n)return 1;
if(cnt == 0) {
ll ans = 1;
for(ll j = 1; j <= n; j++)
ans = ans * j % mod;
sort(z.begin(), z.end());
ll mx = n + 1;
for(int j = 0; j < z.size(); j++) {
ll a = z[j].f - mx;
ans = ans * bp((ll)(z.size() - j), a) % mod;
mx = z[j].f + 1;
}
} else {
ll ans = 1;
sort(z.begin(), z.end());
ll mx = n + 1;
for(int j = 0; j < z.size(); j++) {
ll a = z[j].f - mx;
if(a == 0)continue;
ans = ans * (z.size() - j) % mod;
mx = z[j].f + 1;
}
}
return ans;
}
/*
int gondolaSequence[100001];
int replacementSequence[250001];
int main()
{
int i, n, tag;
int nr;
assert(scanf("%d", &tag)==1);
assert(scanf("%d", &n)==1);
for(i=0;i< n;i++)
assert( scanf("%d", &gondolaSequence[i]) ==1);
switch (tag){
case 1: case 2: case 3:
printf("%d\n", valid(n, gondolaSequence));
break;
case 4: case 5: case 6:
nr = replacement(n, gondolaSequence, replacementSequence);
printf("%d ", nr);
if (nr > 0)
{
for (i=0; i<nr-1; i++)
printf("%d ", replacementSequence[i]);
printf("%d\n", replacementSequence[nr-1]);
}
else printf("\n");
break;
case 7: case 8: case 9: case 10:
printf("%d\n", countReplacement(n, gondolaSequence));
break;
}
return 0;
}
/**/