Submission #128127

#TimeUsernameProblemLanguageResultExecution timeMemory
128127nxteruGondola (IOI14_gondola)C++14
100 / 100
90 ms7284 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define F first #define S second #define PB push_back #define M 1000000009LL ll pw(ll x,ll y){ ll res=1; while(y){ if(y&1)res=res*x%M; y>>=1; x=x*x%M; } return res; } int n,x[100005]; set<int>p; int valid(int N,int a[]){ n=N; int b=-1,c; for(int i=0;i<n;i++){ if(a[i]<=n){ if(b!=-1&&(b+i-c)%n+1!=a[i])return 0; b=a[i]-1,c=i; }else{ if(p.find(a[i])!=p.end())return 0; p.insert(a[i]); } } return 1; } //---------------------- int replacement(int N,int a[],int r[]){ n=N; int b=0,c=0; for(int i=0;i<n;i++)if(a[i]<=n)b=a[i]-1,c=i; for(int i=0;i<n;i++){ x[(c+i)%n]=(b+i)%n+1; } vector<P>g; for(int i=0;i<n;i++)if(a[i]>n)g.PB(P(a[i],i)); sort(g.begin(),g.end()); int d=n+1,k=0; for(int i=0;i<g.size();i++){ int q=g[i].S; while(x[q]<a[q]){ r[k++]=x[q]; x[q]=d++; } } return k; } //---------------------- int countReplacement(int N,int a[]){ n=N; if(valid(n,a)==0)return 0; vector<P>g; for(int i=0;i<n;i++)if(a[i]>n)g.PB(P(a[i],i)); sort(g.begin(),g.end()); ll u=n,s=g.size(),ans=1LL; for(ll i=0;i<s;i++){ ll t=g[i].F; ans=ans*pw(s-i,t-u-1LL)%M; u=t; } if(s==n)ans=ans*ll(n)%M; return ans; }

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g.size();i++){
              ~^~~~~~~~~
#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...