Submission #60817

#TimeUsernameProblemLanguageResultExecution timeMemory
60817hamzqq9Gondola (IOI14_gondola)C++14
100 / 100
127 ms15688 KiB
#include "gondola.h" #define st first #define nd second #define ii pair<int,int> #define pb push_back #define sz(x) (x.size()) #include<bits/stdc++.h> using namespace std; int find_fixed(int n,int inputSeq[]) { int fixed=0; for(int i=0;i<n;i++) { if(inputSeq[i]<=n) { fixed=i; break ; } } return fixed; } int valid(int n, int inputSeq[]) { map<int,int> fr; int fixed=find_fixed(n,inputSeq); int tot=2; int cur=inputSeq[fixed]; for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) { if(cur>n) cur-=n; if(inputSeq[i]>n) { fr[inputSeq[i]]++; continue ; } if(inputSeq[i]!=cur) return 0; } for(auto x:fr) { if(x.nd>1) return 0; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { int fixed=find_fixed(n,gondolaSeq); int cur=(gondolaSeq[fixed]<=n?gondolaSeq[fixed]:1); int tot=2; vector<ii> change; for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) { if(cur>n) cur-=n; if(gondolaSeq[i]>n) { change.pb({gondolaSeq[i],cur}); } } sort(change.begin(),change.end()); int sz=0; int val=n; for(int i=0;i<sz(change);i++) { auto x=change[i]; replacementSeq[sz++]=x.nd; val++; while(val<x.st) { replacementSeq[sz++]=val++; } } return sz; } #define MOD 1000000009 //---------------------- int fe(int x,int y) { if(y==0) return 1; if(y==1) return x; int res=fe(x,y/2); res=1ll*res*res%MOD; if(y&1) return 1ll*res*x%MOD; return res; } int countReplacement(int n, int inputSeq[]) { int isvalid=valid(n,inputSeq); vector<int> ranges; if(!isvalid) return 0; for(int i=0;i<n;i++) { if(inputSeq[i]<=n) continue ; ranges.pb(inputSeq[i]); } int ans=(sz(ranges)==n?n:1); ranges.pb(n); sort(ranges.begin(),ranges.end()); int cursz=sz(ranges)-1; for(int i=1;i<sz(ranges);i++,cursz--) { int range=ranges[i]-ranges[i-1]-1; ans=1ll*ans*fe(cursz,range)%MOD; } return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sz(change);i++) {
               ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:147:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int ans=(sz(ranges)==n?n:1);
                     ^
gondola.cpp:155:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<sz(ranges);i++,cursz--) {
               ^
#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...