제출 #607595

#제출 시각아이디문제언어결과실행 시간메모리
607595PietraLottery (CEOI18_lot)C++14
25 / 100
140 ms65536 KiB
#include<bits/stdc++.h> #define int long long using namespace std ; const int prime = 37 ; const int mod = 1e9 + 7 ; const int maxn = 1e4 + 5 ; int n, l, v[maxn], pot[maxn], inv[maxn], pref[maxn], dist[maxn][maxn], k, q ; void solve(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++){ // dist de i p j if(i == j || i + l - 1 > n || j + l - 1 > n) continue ; int ctr = 0 ; for(int k = 0 ; k < l ; k++) if(v[i+k] != v[j+k]) ctr++ ; dist[i][j] = dist[j][i] = ctr ; } } } int exp(int a, int b){ int ans = 1 ; while(b){ if(b&1) ans = (ans*a)%mod ; a = (a*a)%mod ; b >>= 1 ; } return ans ; } void solve_hash(){ pot[0] = 1LL ; for(int i = 1 ; i < maxn ; i++) pot[i] = (pot[i-1]*prime)%mod ; inv[0] = 1 ; inv[1] = exp(prime, mod-2) ; for(int i = 2 ; i < maxn ; i++) inv[i] = (inv[i-1]*inv[1])%mod ; for(int i = 1 ; i <= n ; i++) pref[i] = (pref[i-1] + (v[i]*pot[i])%mod)%mod ; for(int i = 1 ; i + l - 1 <= n ; i++){ for(int j = 1 ; j + l - 1 <= n ; j++){ if(i == j) continue ; int v1 = pref[i+l-1] ; int v2 = pref[j+l-1] ; if(i - 1 >= 1) v1 = (v1 - pref[i-1] + mod)%mod ; if(j - 1 >= 1) v2 = (v2 - pref[j-1] + mod)%mod ; v1 = (v1*inv[i])%mod, v2 = (v2*inv[j])%mod ; if(v1 == v2) dist[i][j] = dist[j][i] = 1 ; } } for(int i = 1 ; i + l - 1 <= n ; i++){ int ct = 0 ; for(int j = 1 ; j + l - 1 <= n ; j++){ if(i == j) continue ; if(dist[i][j] == 1) ct++ ; } cout << ct << " " ; } cout << "\n" ; } int32_t main(){ ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; cin >> n >> l ; for(int i = 1 ; i <= n ; i++) cin >> v[i] ; // for(int i = 1 ; i <= n ; i++){ // for(int j = 1 ; j <= n ; j++){ // cout << dist[i][j] <<" " ; // } // cout << "\n" ; // } cin >> q ; cin >> k ; if(q == 1 && !k){ solve_hash() ; exit(0) ; } solve() ; for(int i = 1 ; i + l - 1 <= n ; i++){ int ct = 0 ; for(int j = 1 ; j + l - 1 <= n ; j++) if(i != j && dist[i][j] <= k) ct++ ; cout << ct << " " ; } cout << "\n" ; for(int i = 1 ; i < q ; i++){ cin >> k ; for(int i = 1 ; i + l - 1 <= n ; i++){ int ct = 0 ; for(int j = 1 ; j + l - 1 <= n ; j++) if(i != j && dist[i][j] <= k) ct++ ; cout << ct << " " ; } cout << "\n" ; } }
#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...