| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 422302 | APROHACK | 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 PB push_back#define S second#define F firstusing namespace std; int valid(int n, int inputSeq[]){ bool ocurr[250001]; for(int i = 0 ; i < 250001 ; i++){ ocurr[i]=false; } //bool pst=false; int cur=-1; for(int i = 0 ; i < n ; i++){ if(ocurr[inputSeq[i]]){ return 0; } ocurr[inputSeq[i]]=true; if(inputSeq[i]<=n){ if(cur==-1){ cur=inputSeq[i]; }else{ if(inputSeq[i]!=cur)return 0; } } if(cur!=-1)cur++; if(cur==n+1)cur=1; } return 1;} //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]){ int pos=-1; vector<pair<int, int> >wow; int mascara[n]; for(int i = 0 ; i < n ; i++){ if(gondolaSeq[i]>n){ wow.PB({gondolaSeq[i], i}); }else{ pos=i; } } int cur=gondolaSeq[pos]; for(int i = pos ; i >=0 ; i--){ mascara[i]=cur; cur--; if(cur==0)cur=n; } cur=gondolaSeq[pos]; for(int i = pos ; i <n ; i++){ mascara[i]=cur; cur++; if(cur==n+1)cur=1; } int l, p=n+1, indx=0; sort(wow.begin(), wow.end());//numero, indice for(int i = 0 ; i < wow.size(); i++){ while(mascara[wow[i].S]<wow[i].F){ replacementSeq[indx]=mascara[wow[i].S]; mascara[wow[i].S]=p; //cout<<replacementSeq[indx]<<endl; p++; indx++; } } return indx;} //---------------------- int countReplacement(int n, int inputSeq[]){ if(valid(n, inputSeq)==0)return 0; vector<int >whew; int mxcur=n; bool fixed=false; for(int i = 0 ; i < n ; i++){ if(inputSeq[i]>n){ whew.PB(inputSeq[i]); }else{ fixed=true; } } long long rta = 1, MOD = 1000000007; sort(whew.begin(), whew.end()); for(int i = 0 ; i < whew.size() ; i++){ int nxt=(whew[i]), nums; nums=(nxt-1)-(mxcur); if(nums!=0&&(whew.size()-i)>1)rta*=((nums%MOD)*(whew.size()-i))%MOD; rta%=MOD; mxcur=nxt; //wow.pop(); } if(!fixed){ rta*=n; rta%=MOD; } return rta;}#include <bits/stdc++.h>#define PB push_back#define S second#define F firstusing namespace std; int valid(int n, int inputSeq[]){ bool ocurr[250001]; for(int i = 0 ; i < 250001 ; i++){ ocurr[i]=false; } //bool pst=false; int cur=-1; for(int i = 0 ; i < n ; i++){ if(ocurr[inputSeq[i]]){ return 0; } ocurr[inputSeq[i]]=true; if(inputSeq[i]<=n){ if(cur==-1){ cur=inputSeq[i]; }else{ if(inputSeq[i]!=cur)return 0; } } if(cur!=-1)cur++; if(cur==n+1)cur=1; } return 1;} //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]){ int pos=-1; vector<pair<int, int> >wow; int mascara[n]; for(int i = 0 ; i < n ; i++){ if(gondolaSeq[i]>n){ wow.PB({gondolaSeq[i], i}); }else{ pos=i; } } int cur=gondolaSeq[pos]; for(int i = pos ; i >=0 ; i--){ mascara[i]=cur; cur--; if(cur==0)cur=n; } cur=gondolaSeq[pos]; for(int i = pos ; i <n ; i++){ mascara[i]=cur; cur++; if(cur==n+1)cur=1; } int l, p=n+1, indx=0; sort(wow.begin(), wow.end());//numero, indice for(int i = 0 ; i < wow.size(); i++){ while(mascara[wow[i].S]<wow[i].F){ replacementSeq[indx]=mascara[wow[i].S]; mascara[wow[i].S]=p; //cout<<replacementSeq[indx]<<endl; p++; indx++; } } return indx;} //---------------------- int countReplacement(int n, int inputSeq[]){ if(valid(n, inputSeq)==0)return 0; vector<int >whew; int mxcur=n; bool fixed=false; for(int i = 0 ; i < n ; i++){ if(inputSeq[i]>n){ whew.PB(inputSeq[i]); }else{ fixed=true; } } long long rta = 1, MOD = 1000000007; sort(whew.begin(), whew.end()); for(int i = 0 ; i < whew.size() ; i++){ int nxt=(whew[i]), nums; nums=(nxt-1)-(mxcur); if(nums!=0&&(whew.size()-i)>1)rta*=((nums%MOD)*(whew.size()-i))%MOD; rta%=MOD; mxcur=nxt; //wow.pop(); } if(!fixed){ rta*=n; rta%=MOD; } return rta;}#include <bits/stdc++.h>#define PB push_back#define S second#define F firstusing namespace std; int valid(int n, int inputSeq[]){ bool ocurr[250001]; for(int i = 0 ; i < 250001 ; i++){ ocurr[i]=false; } //bool pst=false; int cur=-1; for(int i = 0 ; i < n ; i++){ if(ocurr[inputSeq[i]]){ return 0; } ocurr[inputSeq[i]]=true; if(inputSeq[i]<=n){ if(cur==-1){ cur=inputSeq[i]; }else{ if(inputSeq[i]!=cur)return 0; } } if(cur!=-1)cur++; if(cur==n+1)cur=1; } return 1;} //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]){ int pos=-1; vector<pair<int, int> >wow; int mascara[n]; for(int i = 0 ; i < n ; i++){ if(gondolaSeq[i]>n){ wow.PB({gondolaSeq[i], i}); }else{ pos=i; } } int cur=gondolaSeq[pos]; for(int i = pos ; i >=0 ; i--){ mascara[i]=cur; cur--; if(cur==0)cur=n; } cur=gondolaSeq[pos]; for(int i = pos ; i <n ; i++){ mascara[i]=cur; cur++; if(cur==n+1)cur=1; } int l, p=n+1, indx=0; sort(wow.begin(), wow.end());//numero, indice for(int i = 0 ; i < wow.size(); i++){ while(mascara[wow[i].S]<wow[i].F){ replacementSeq[indx]=mascara[wow[i].S]; mascara[wow[i].S]=p; //cout<<replacementSeq[indx]<<endl; p++; indx++; } } return indx;} //---------------------- int countReplacement(int n, int inputSeq[]){ if(valid(n, inputSeq)==0)return 0; vector<int >whew; int mxcur=n; bool fixed=false; for(int i = 0 ; i < n ; i++){ if(inputSeq[i]>n){ whew.PB(inputSeq[i]); }else{ fixed=true; } } long long rta = 1, MOD = 1000000007; sort(whew.begin(), whew.end()); for(int i = 0 ; i < whew.size() ; i++){ int nxt=(whew[i]), nums; nums=(nxt-1)-(mxcur); if(nums!=0&&(whew.size()-i)>1)rta*=((nums%MOD)*(whew.size()-i))%MOD; rta%=MOD; mxcur=nxt; //wow.pop(); } if(!fixed){ rta*=n; rta%=MOD; } return rta;}