| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 793008 | MODDI | 곤돌라 (IOI14_gondola) | C++17 | 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 "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
int valid(int n, int inputSeq[])
{
int pos = -1;
for(int i = 0; i < n; i++){
if(inputSeq[i] == 1){
pos = i;
break;
}
}
bool seq = true;
int at = 1, lim = pos;
while(pos < n){
if(inputSeq[pos] == at){
pos++;
at++;
}
else{
seq = false;
break;
}
}
if(!seq) return 0;
pos = 0;
while(pos < lim){
if(inputSeq[pos] == at){
pos++;
at++;
}
else{
seq = false;
break;
}
}
if(!seq) return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int pos = -1;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] >= 1 && gondolaSeq[i] <= n){
pos = i;
break;
}
}
if(pos == -1){
vector<pii> arr(n);
for(int i = 0; i < n; i++){
arr[i] = mp(gondolaSeq[i], i);
}
sort(arr.begin(), arr.end());
int j = 0, rez = 0, here = 1, at = n + 1;
int pos = arr[0].second, need[n];
for(int i = pos; i < n; i++) need[i] = here++;
for(int i = 0; i < pos; i++) need[i] = here++;
for(int i = 0; i < (int)arr.size(); i++){
int where = arr[i].second, val = arr[i].first;
replacementSeq[j++] = need[where];
rez++;
while(at < val){
replacementSeq[j++] = at++;
rez++;
}
at++;
}
return rez;
}
else{
int need[n];
bool done[n+1];
memset(done, false, sizeof done);
int at = gondolaSeq[pos];
while(at <= n){
at++;
pos++; pos%=n;
}
int here = 1;
for(int i = pos; i < n; i++) need[i] = here++;
for(int i = 0; i < pos; i++) need[i] = here++;
vector<pii> arr;
for(int i = 0; i < n; i++){
if(need[i] == gondolaSeq[i]) done[need[i]] = true;
else{
arr.pb(mp(gondolaSeq[i], i));
}
}
sort(arr.begin(), arr.end());
at = n + 1;
int j = 0, rez = 0;
for(int i = 0; i < (int)arr.size(); i++){
int where = arr[i].second, val = arr[i].first;
replacementSeq[j++] = need[where];
rez++;
while(at < val){
replacementSeq[j++] = at++;
rez++;
}
at++;
}
return rez;
}
}
const int mod = 1000000009;
ll calculate(ll step, ll base){
ll res = 1;
base %= mod;
if(base == 0) return 0;
while(step > 0){
if(step & 1)
res = (res * base) % mod;
step = step>>1;
base = (base*base) % mod;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
//int checker = valid(n, inputSeq);
vector<pii> arr;
int pos = -1;
for(int i = 0; i < n; i++){
arr.pb(mp(inputSeq[i], i));
if(inputSeq[i] >= 1 && inputSeq[i] <= n) pos = i;
}
if(pos != -1){
int at = inputSeq[pos];
while(at <= n){
at++;
pos++;
pos%=n;
}
int skipped = 0;
at=1;
bool ok = true;
for(int i = pos; i < n; i++){
if(inputSeq[i] == at+skipped){
at++;
skipped = 0;
}
else if(inputSeq[i] <= n && at + skipped > inputSeq[i]){
ok = false;
}
else
skipped++;
}
//cout<<"OK: "<<ok<<endl;
if(!ok) return 0;
}
vi niz;
int where = n+1;
for(int i = 0; i < n; i++){
if(inputSeq[i] > n) niz.pb(inputSeq[i]);
}
sort(niz.begin(), niz.end());
ll ways = 1;
for(int i = 0; i < (int)niz.size(); i++){
if(i == 0 && niz[i] > n) ways = n;
while(where < niz[i]){
ways *= ((int)niz.size()-i)*1LL;
ways %= mod;
where++;
}
if(where == niz[i]) where++;
}
return (int)ways;
}