| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 422299 | APROHACK | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;}