제출 #111400

#제출 시각아이디문제언어결과실행 시간메모리
111400CodeKracker곤돌라 (IOI14_gondola)C++14
60 / 100
34 ms4368 KiB
/*input 2 3 4 */ /** Author: Kristopher Paul Date Created: 15-05-2019 Contest Name: _/ _/ _/_/_/_/ _/ _/_/_/_/ _/ _/ _/ _/ _/ _/ _/_/ _/_/_/_/ _/ _/_/_/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/_/_/ **/ #include <gondola.h> #include<bits/stdc++.h> #define ll long long //#define int ll #define pb push_back #define INF 0x3f3f3f3f //0x3f3f3f3f = 63 #define MOD 1000000009 #define mp make_pair const double PI=3.141592653589793238462643383279502884197169399375105820974944; #define REP(i,n) for (int i = 0; i < n; i++) #define FOR(i,a,b) for (int i = a; i < b; i++) #define REPD(i,n) for (int i = n-1; i >= 0; i--) #define FORD(i,a,b) for (int i = a; i >= b; i--) #define remax(a,b) a = max(a,b) #define remin(a,b) a = min(a,b) #define umap unordered_map #define pii pair<int,int> #define F first #define S second #define mii map<int,int> #define vi vector<int> #define vvi vector<vi> #define itr :: iterator it #define all(v) v.begin(),v.end() #define WL(t) while(t--) #define gcd(a,b) __gcd((a),(b)) #define lcm(a,b) ((a)*(b))/gcd((a),(b)) #define out(x) cout << #x << " is " << x << endl #define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; int ModExp(int x,int y,int m){ int res = 1; x = x % m; while (y > 0) { if (y & 1) res = (res*x) % m; y = y>>1; x = (x*x) % m; } return res; } int valid(int n, int arr[]){ int mini = n+1; int pos = n; umap<int,int> cnt; FOR(i,0,n){ cnt[arr[i]]++; if(cnt[arr[i]] > 1){ return 0; } if(arr[i] < mini){ mini = arr[i]; pos = i; } } if(mini > n){ return 1; } int to[n]; int val = arr[pos]; FOR(i,pos,n){ to[i] = val; if(arr[i] <= n && arr[i] != to[i]){ return 0; } val++; if(val == n+1){ val = 1; } } FOR(i,0,pos){ to[i] = val; if(arr[i] <= n && arr[i] != to[i]){ return 0; } val++; if(val == n+1){ val = 1; } } return 1; } int replacement(int n, int arr[], int replacementSeq[]){ int mini = n+1; int pos = 0; FOR(i,0,n){ if(arr[i] < mini){ mini = arr[i]; pos = i; } } vector<pii> vec; if(mini > n){ FOR(i,0,n){ vec.pb({arr[i],i+1}); } }else{ int v = mini; FOR(i,pos,n){ if(arr[i] > n){ vec.pb({arr[i],v}); } v++; if(v == n+1){ v = 1; } } FOR(i,0,pos){ if(arr[i] > n){ vec.pb({arr[i],v}); } v++; if(v == n+1){ v = 1; } } } sort(vec.begin(),vec.end()); int st = n+1; int ind = 0; FOR(i,0,vec.size()){ int cur = vec[i].first; int lv = vec[i].second; FOR(j,st,cur+1){ replacementSeq[ind] = lv; lv = j; ind++; } st = cur+1; } return ind; } int countReplacement(int n, int arr[]){ if(!valid(n,arr)){ return 0; } int maxi = 0; int mini = n+1; int pos = 0; FOR(i,0,n){ remax(maxi,arr[i]); if(arr[i] < mini){ mini = arr[i]; pos = i; } } if(maxi <= n){ return 1; } vector<int> vec; FOR(i,0,n){ if(arr[i] > n){ vec.pb(arr[i]); } } sort(vec.begin(),vec.end()); int st = n+1; vector<ll> sz; ll cur = 0; FOR(i,0,vec.size()){ cur += vec[i]-st; if(cur > 0){ sz.pb(cur); } st = vec[i]+1; } ll ans = 1; int lv = 1; FOR(i,0,sz.size()){ if(sz[i] < lv){ continue; } ans *= ModExp((sz.size()-i),(sz[i]-lv+1),MOD); ans %= MOD; lv = sz[i]+1; } if(mini > n){ ans *= n; ans %= MOD; } ans %= MOD; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:25:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for (int i = a; i < b; i++)
gondola.cpp:140:9:
     FOR(i,0,vec.size()){
         ~~~~~~~~~~~~~~                
gondola.cpp:140:5: note: in expansion of macro 'FOR'
     FOR(i,0,vec.size()){
     ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:25:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for (int i = a; i < b; i++)
gondola.cpp:180:9:
     FOR(i,0,vec.size()){
         ~~~~~~~~~~~~~~                
gondola.cpp:180:5: note: in expansion of macro 'FOR'
     FOR(i,0,vec.size()){
     ^~~
gondola.cpp:25:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b) for (int i = a; i < b; i++)
gondola.cpp:189:9:
     FOR(i,0,sz.size()){
         ~~~~~~~~~~~~~                 
gondola.cpp:189:5: note: in expansion of macro 'FOR'
     FOR(i,0,sz.size()){
     ^~~
gondola.cpp:159:9: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
     int pos = 0;
         ^~~
#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...