제출 #291373

#제출 시각아이디문제언어결과실행 시간메모리
291373georgerapeanu곤돌라 (IOI14_gondola)C++11
90 / 100
23 ms2944 KiB
#include "gondola.h" #include <cstdio> #include <algorithm> using namespace std; inline int get_in_range(int st,int dr,int val){ int tmp = (val - st) % (dr - st + 1); if(tmp < 0){ tmp += (dr - st + 1); } return tmp + st; } int stuff[250005]; int valid(int n, int inputSeq[]) { int pos = -1; for(int i = 0;i < n;i++){ if(inputSeq[i] <= n){ pos = i; } stuff[inputSeq[i]]++; if(stuff[inputSeq[i]] > 1){ return 0; } } for(int i = 0;i < n;i++){ if(inputSeq[i] <= n && inputSeq[i] != get_in_range(1,n,inputSeq[pos] + i - pos)){ return 0; } } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { for(int i = 0;i <= 2e5;i++){ stuff[i] = -1; } int ma = 0,ma_pos; int pos = -1; for(int i = 0;i < n;i++){ stuff[gondolaSeq[i]] = i; ma = max(ma,gondolaSeq[i]); if(ma == gondolaSeq[i]){ ma_pos = i; } if(gondolaSeq[i] <= n){ pos = i; } } if(pos == -1){ pos = 0; gondolaSeq[pos] = 1; } for(int i = 0;i < n;i++){ gondolaSeq[i] = get_in_range(1,n,gondolaSeq[pos] + i - pos); } int len = 0; for(int i = n + 1;i <= ma;i++){ if(stuff[i] == -1){ replacementSeq[len++] = gondolaSeq[ma_pos]; gondolaSeq[ma_pos] = i; } else{ replacementSeq[len++] = gondolaSeq[stuff[i]]; gondolaSeq[stuff[i]] = i; } } return len; } //---------------------- const int MOD = 1e9 + 9; int lgpow(int b,int e){ int p = 1; while(e){ if(e & 1){ p = 1LL * p * b % MOD; } b = 1LL * b * b % MOD; e >>= 1; } return p; } int countReplacement(int n, int inputSeq[]) { if(valid(n,inputSeq) == 0){ return 0; } int ans = n; for(int i = 0;i < n;i++){ if(inputSeq[i] <= n){ ans = 1; } } sort(inputSeq,inputSeq + n); for(int i = n - 1;i >= 0;i--){ if(inputSeq[i] <= n){ break; } int curr = inputSeq[i]; int nxt = ((i == 0 || inputSeq[i - 1] < n) ? n:inputSeq[i - 1]); ans = 1LL * ans * lgpow(n - i,curr - nxt - 1) % MOD; } return ans; }

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

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:77:48: warning: 'ma_pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             replacementSeq[len++] = gondolaSeq[ma_pos];
      |                                                ^~~~~~
#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...