# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1027633 | MarwenElarbi | Gondola (IOI14_gondola) | C++17 | 57 ms | 9556 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;
#define pb push_back
#define se second
#define fi first
const int nax=5e5+5;
const int MOD=1e9+9;
int valid(int n, int inputSeq[])
{
vector<pair<int,int>> tab;
bool test=true;
set<int> stt;
for (int i = 0; i < n; ++i)
{
stt.insert(inputSeq[i]);
}
test&=(stt.size()==n);
int cnt=-1e9;
for (int i = 0; i < n; ++i)
{
if(inputSeq[i]<=n){
cnt=(inputSeq[i]-(i+1)+n)%n;
}
}
if(cnt==-1e9) return test;
for (int i = 0; i < n; ++i)
{
if(inputSeq[i]<=n){
if((inputSeq[i]-(i+1)+n)%n!=cnt) test=false;
}
}
return test;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<pair<int,int>> tab;
for (int i = 0; i < n; ++i)
{
if(gondolaSeq[i]>n){
tab.pb({gondolaSeq[i],i+1});
}
}
if(tab.size()==n){
sort(tab.begin(),tab.end());
int cnt=n;
int cur=0;
for (int i = 0; i < tab.size(); ++i)
{
replacementSeq[cur++]=tab[i].se;
cnt++;
while(cnt<tab[i].fi){
replacementSeq[cur++]=cnt++;
}
}
return cur;
}else{
int a=0;
for (int i = 0; i < n; ++i)
{
if(gondolaSeq[i]<=n) a=(gondolaSeq[i]-(i+1)+n)%n;
}
sort(tab.begin(),tab.end());
int cnt=n;
int cur=0;
for (int i = 0; i < tab.size(); ++i)
{
replacementSeq[cur++]=(tab[i].se+a == 0 ? n : tab[i].se+a);
cnt++;
while(cnt<tab[i].fi){
replacementSeq[cur++]=cnt++;
}
}
return cur;
}
}
//----------------------
long long binpow(long long x,long long m){
x%=MOD;
long long res=1;
while(m){
if(m%2) res=res*x%MOD;
x=x*x%MOD;
m/=2;
}
return res;
}
int countReplacement(int n, int inputSeq[])
{
long long cur=1;
set<int> st;
if(!valid(n,inputSeq)) return 0;
for (int i = 0; i < n; ++i)
{
st.insert(i);
}
for (int i = 0; i < n; ++i)
{
if(inputSeq[i]<=n) st.erase(inputSeq[i]);
}
if(st.size()==0) return 1;
set<int> stt;
for (int i = 0; i < n; ++i)
{
if(inputSeq[i]>n) stt.insert(inputSeq[i]);
}
int cnt=n;
if(stt.size()==n) cur=n;
while(stt.size()){
//cout <<cnt<<endl;
cur*=binpow(stt.size(),*stt.begin()-1-cnt)%MOD;
cur%=MOD;
cnt=*stt.begin();
stt.erase(*stt.begin());
}
return cur;
}
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... |