Submission #964309

#TimeUsernameProblemLanguageResultExecution timeMemory
964309maxFedorchukGondola (IOI14_gondola)C++17
60 / 100
26 ms5124 KiB
#include <bits/stdc++.h> using namespace std; #include "gondola.h" int valid(int n, int inputSeq[]) { set < int > st; int p=0; for(int i=0;i<n;i++) { if(inputSeq[i]<=n) { p=(n+i-inputSeq[i])%n; } st.insert(inputSeq[i]); } if(st.size()!=n) { return 0; } for(int i=0;i<n;i++) { if(inputSeq[i]<=n) { if((n+i-inputSeq[i])%n!=p) { return 0; } } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int ned_to_be[n],in=-1; for(int i=0;i<n;i++) { if(gondolaSeq[i]<=n) { ned_to_be[i]=gondolaSeq[i]; in=i; break; } } if(in!=-1) { int nd=ned_to_be[in]; for(int i=(in+1)%n;i!=in;i=(i+1)%n) { nd%=n; nd++; ned_to_be[i]=nd; } } else { for(int i=0;i<n;i++) { ned_to_be[i]=i+1; } } map < int , int > mp; int mx=0; for(int i=0;i<n;i++) { if(gondolaSeq[i]>mx) { mx=gondolaSeq[i]; in=i; } if(gondolaSeq[i]>n) { mp[gondolaSeq[i]]=ned_to_be[i]; } } int uk=0; for(int i=n+1;i<=mx;i++,uk++) { if(mp.find(i)==mp.end() || i==mx) { replacementSeq[uk]=ned_to_be[in]; ned_to_be[in]=i; } else { replacementSeq[uk]=mp[i]; } } return uk; } //---------------------- const long long MOD=1e9+7; long long binpow(long long a,long long b) { long long rt=1; while(b) { if(b&1) { rt=(rt*a)%MOD; } a=(a*a)%MOD; b/=2; } return rt; } int countReplacement(int n, int inputSeq[]) { if(!valid(n,inputSeq)) { return 0; } set < long long > st; for(long long i=0;i<n;i++) { if(inputSeq[i]>n) { st.insert(inputSeq[i]); } } long long mun=n,ans=1,k=st.size(); for(auto u:st) { //cout<<u<<" "<<k<<" "<<u-mun-1<<"\n"; ans=(ans*binpow(k,u-mun-1))%MOD; k--; mun=u; } if(st.size()==n) { ans=(ans*n)%MOD; } return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(st.size()!=n)
      |        ~~~~~~~~~^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:155:17: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  155 |     if(st.size()==n)
      |        ~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...