제출 #247531

#제출 시각아이디문제언어결과실행 시간메모리
247531Evirir곤돌라 (IOI14_gondola)C++17
75 / 100
25 ms3504 KiB
#include "gondola.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 1e9+9; bool DEBUG = 0; const int MAXN = 100005; const int MAXA = 250005; ll add(ll a, ll b) { a+=b; a%=MOD; if(a<0) a+=MOD; return a; } ll mult(ll a, ll b) { if(a>MOD) a%=MOD; if(b>MOD) b%=MOD; ll ans=(a*b)%MOD; if(ans<0) ans+=MOD; return ans; } int valid(int n, int inputSeq[]) { int minid=0; forn(i,0,n){ if(inputSeq[minid]>inputSeq[i]){ minid=i; } } int tmp[n]; forn(i,0,n){ tmp[i]=inputSeq[(minid+i)%n]; } forn(i,0,n) inputSeq[i]=tmp[i]; bool used[MAXA]{}; int last=-1; for(int i=0;i<n;i++){ if(used[inputSeq[i]]) return 0; used[inputSeq[i]]=1; if(inputSeq[i]<=n){ if(last!=-1 && inputSeq[i]-inputSeq[last]!=i-last) return 0; last=i; } } return 1; } int replacement(int n, int gondolaSeq[], int replacementSeq[]) { assert(valid(n, gondolaSeq)); int loc[MAXA]; mset(loc,-1); int large=0; for(int i=0;i<n;i++){ loc[gondolaSeq[i]]=i; if(gondolaSeq[i]>gondolaSeq[large]){ large=i; } } int a[n]; int start=0,val=1; for(int i=0;i<n;i++){ if(gondolaSeq[i]<=n){ start=i; val=gondolaSeq[i]; break; } } for(int i=start;;){ a[i]=val++; if(val==n+1) val=1; i=(i+1)%n; if(i==start) break; } int ptr=0; for(int i=n+1;i<=gondolaSeq[large];i++){ if(loc[i] == -1){ //cout<<"Not found\n"; replacementSeq[ptr++]=a[large]; a[large]=i; } else{ //cout<<"Found\n"; replacementSeq[ptr++] = a[loc[i]]; a[loc[i]]=i; } } return ptr; } int countReplacement(int n, int inputSeq[]) { if(!valid(n, inputSeq)) return 0; ll ans=1; int loc[MAXA]; mset(loc,-1); for(int i=0;i<n;i++){ loc[inputSeq[i]]=i; } int Max=-1; forn(i,0,n){ Max=max(Max, inputSeq[i]); } ll cur=0; forn(i,0,n){ if(inputSeq[i]>n) cur++; } for(int i=n+1;i<=Max;i++){ if(loc[i] != -1) cur--; else ans=mult(ans, cur); } return ans; }
#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...