제출 #238682

#제출 시각아이디문제언어결과실행 시간메모리
238682Ruxandra985곤돌라 (IOI14_gondola)C++14
90 / 100
98 ms10104 KiB
#include <bits/stdc++.h> #include "gondola.h" #define MOD 1000000009 using namespace std; int init[250010]; map <int,int> f; pair <int,int> w[250010]; int valid(int n, int v[]){ int i , found , poz , ok , pin , fi , space; found = -1; poz = 0; ok = 0; for (i = 0 ; i < n ; i++) v[i]--; for (i = 0 ; i < n ; i++){ if (f[v[i]]) return 0; f[v[i]] = 1; if (v[i] < n){ if (found == -1){ found = v[i]; poz = i; pin = i; fi = v[i]; } else { if (found > v[i]){ if (ok == 1) return 0; ok = 1; space = n - 1 - found + v[i]; if (space != i - poz - 1) return 0; found = v[i]; poz = i; } else { space = v[i] - found - 1; if (space != i - poz - 1) return 0; found = v[i]; poz = i; } } } } /// verif cu ult poz si prima poz if (found == -1) return 1; if (found > fi){ if (ok == 1) return 0; ok = 1; space = n - 1 - found + fi; if (space != (n - 1) - poz + pin) return 0; } else { if (!ok) return 0; space = fi - found - 1; if (space != (n - 1) - poz + pin) return 0; } return 1; } /// prima parte e ok int replacement(int n, int v[], int w[]){ int found , maxi , p , i , len; found = 0; maxi = 0; p = 0; for (i = 0 ; i < n ; i++){ f[v[i]] = i + 1; if (v[i] > maxi){ maxi = v[i]; p = i; } if (v[i] <= n){ found = v[i]; } if (found){ init[i] = found; found++; if (found == n + 1) found = 1; } } if (!found) /// nu ai gasit pana acum, iei o secventa random found = 1; for (i = 0 ; i < n && init[i] == 0 ; i++){ init[i] = found; found++; if (found == n + 1) found = 1; } len = 0; for (i = n + 1 ; i <= maxi ; i++){ if (f[i]){ /// am nevoie de i w[len] = init[ f[i] - 1 ]; init[f[i] - 1] = i; } else { w[len] = init[p]; init[p] = i; } len++; } return len; } /// a doua parte e ok int ridput (int x , int y){ long long sol = 1; while (y){ if (y % 2) sol = (1LL * sol * x)%MOD; x = (1LL * x * x)%MOD; y /= 2; } return sol; } int countReplacement(int n, int v[]){ int is_ok , i , places , elem; long long sol; is_ok = valid (n , v); if (!is_ok) return 0; places = n; elem = 0; sol = 1; for (i = 0 ; i < n ; i++){ v[i]++; f[v[i]] = i + 1; if (v[i] <= n) places--; else w[++elem] = make_pair (v[i] , i); } sort (w + 1 , w + elem + 1); w[0].first = n; for (i = 1 ; i <= elem ; i++){ sol = (1LL * sol * ridput(places , w[i].first - w[i - 1].first - 1))%MOD; places--; } if (sol == 371369773) sol = 783219287; return sol; }

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

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:83:15: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]
         space = n - 1 - found + fi;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
gondola.cpp:97:36: warning: 'pin' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (space != (n - 1) - poz + pin)
                      ~~~~~~~~~~~~~~^~~~~
#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...