제출 #182564

#제출 시각아이디문제언어결과실행 시간메모리
182564FieryPhoenix곤돌라 (IOI14_gondola)C++11
60 / 100
46 ms4228 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> #include <map> #include <queue> #include <set> #include <iomanip> #include <deque> #include <cassert> #include <ctime> #include <cstring> #include <cstdlib> #include <chrono> #include <ctime> #include <random> #include <stack> #include <unordered_set> #include <unordered_map> #include <iterator> #include <climits> #include "gondola.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000009 int valid(int N, int arr[]){ unordered_set<int>st; int pos=-1; for (int i=0;i<N;i++){ if (st.count(arr[i])) return 0; st.insert(arr[i]); if (arr[i]<=N) pos=i; } if (pos==-1) return 1; for (int i=0;i<N;i++){ int j=(pos+i)%N; int target=arr[pos]+i; if (target>N) target-=N; if (arr[j]<=N && arr[j]!=target) return 0; } return 1; } bool used[250001]; int should[100001]; int replacement(int N, int g[], int repl[]){ int nex=0; for (int i=0;i<N;i++){ should[i]=i+1; nex=max(nex,g[i]); } int pos=-1; for (int i=0;i<N;i++) if (g[i]<=N) pos=i; for (int i=pos;i<pos+N;i++){ int x=g[pos]+i-pos; if (x>N) x-=N; should[i%N]=x; } vector<int>v; for (int i=0;i<N;i++) used[g[i]]=true; priority_queue<pair<int,int>>pq; for (int i=0;i<N;i++) pq.push({g[i],i}); while (!pq.empty()){ int ind=pq.top().second; pq.pop(); if (g[ind]<=N) continue; while (used[nex]) nex--; if (nex<=N) nex=should[ind]; v.push_back(nex); used[nex]=true; g[ind]=nex; pq.push({g[ind],ind}); } reverse(v.begin(),v.end()); for (int i=0;i<(int)v.size();i++) repl[i]=v[i]; return (int)v.size(); } int countReplacement(int n, int a[]){ if (valid(n,a)==0) return 0; ll ans=1; vector<int>v; int mx=0; for (int i=0;i<n;i++) if (a[i]>n){ mx=max(mx,a[i]); v.push_back(a[i]); } sort(v.begin(),v.end()); for (int i=(int)v.size()-1;i>=0;i--){ ll r=v[i]-1; ll l=n+1; if (i>0) l=v[i-1]+1; if (r>=l){ int num=(int)v.size()-i; ans=(ans*(num*(r-l+1)))%MOD; } } int pos=-1; for (int i=0;i<n;i++) if (a[i]<=n) pos=i; if (pos==-1) ans=(ans*n)%MOD; 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...