#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,l,q,k;
cin >> n >> l;
int tab[n];
for (int i=0; i<n; i++){
cin >> tab[i];
}
cin >> q;
cin >> k;
if (q==1 && k==0){
int akt=1,pop=-1;
map<int,int> mapa;
for (int i=0; i<n; i++){
if (mapa.find(tab[i])==mapa.end()){
mapa[tab[i]] = akt;
akt++;
}
tab[i] = mapa[tab[i]];
}
int P=12553;
int MOD=1e9+7;
int P_[n];
P_[0] = 1;
for (int i=1; i<n; i++){
P_[i] = ((long long)P_[i-1]*P)%MOD;
}
int hash[n];
hash[0] = tab[0];
for (int i=1; i<n; i++){
hash[i] = (hash[i-1]+((long long)tab[i]*P_[i])%MOD)%MOD;
//cout << tab[i] << " " << i << " " << P_[i] << " " << hash[i-1] << endl;
}
// for (auto i : hash) cout << i << " ";
//cout << endl;
for (int i=0; i<(n-l+1); i++){
int wynik=0;
for (int j=0; j<(n-l+1); j++){
if (j==i) continue;
int hash_1 = hash[i+l-1];
int hash_2 = hash[j+l-1];
if (i>0) hash_1-=hash[i-1];
if (j>0) hash_2-=hash[j-1];
//cout << i << " " << j << " " << hash_1 << " " << hash_2 << endl;
if (i > j){
hash_2 = ((long long)hash_2*P_[i-j])%MOD;
}
else{
hash_1 = ((long long)hash_1*P_[j-i])%MOD;
}
//cout << i << " " << j << " " << hash_1 << " " << hash_2 << endl;
if (hash_1==hash_2) wynik++;
}
cout << wynik << " ";
}
}
else{
int odp[(n-l+1)][l+1];
map<pair<int,int>,vector<int>> mapa;
for (int i=0; i<(n-l+1); i++){
for (int j=0; j<l; j++){
if (mapa.find({j,tab[i+j]}) != mapa.end()){
mapa[{j,tab[i+j]}].push_back(i);
}
else{
mapa[{j,tab[i+j]}] = {i};
}
}
}
for (int i=0; i<(n-l+1); i++){
int wyniki_2[n];
for (int s=0; s<n; s++) wyniki_2[s] = 0;
for (int j=i; j<(i+l); j++){
for (int s : mapa[{j-i,tab[j]}]){
if (i==s) continue;
//cout << i << " " << " " << tab[j] << " " << s << endl;
wyniki_2[s]++;
}
}
vector<int> wyniki(0);
int maxi=0;
for (int s=0; s<(n-l+1); s++){
if (i==s) continue;
//cout << s << ": " << wyniki_2[s] << " ";
wyniki.push_back(wyniki_2[s]);
}
//cout << endl;
sort(wyniki.begin(),wyniki.end());
//for (auto x : wyniki) cout << x << " ";cout << endl;
int ile=(n-l);
int wsk=0;
for (int x=l; x>=0; x--){
//if (wsk<(n-l)) cout << x << " " << ile << " " << wsk << " " << wyniki[wsk] << endl;
odp[i][x] = ile;
//cout << odp[i][x] << endl;
while (wsk < (n-l) && l-wyniki[wsk]==x) {ile--; wsk++;}
}
}
for (int j=0; j<(n-l+1); j++){
cout << odp[j][k]<< " ";
}
cout << endl;
for (int i=1; i<q; i++){
cin >> k;
for (int j=0; j<(n-l+1); j++){
cout << odp[j][k]<< " ";
}
cout << endl;
}
}
return 0;
}
Compilation message
lot.cpp: In function 'int main()':
lot.cpp:20:19: warning: unused variable 'pop' [-Wunused-variable]
20 | int akt=1,pop=-1;
| ^~~
lot.cpp:115:17: warning: unused variable 'maxi' [-Wunused-variable]
115 | int maxi=0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
424 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1112 KB |
Output is correct |
| 9 |
Correct |
6 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
604 KB |
Output is correct |
| 11 |
Correct |
2 ms |
604 KB |
Output is correct |
| 12 |
Correct |
5 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
424 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1112 KB |
Output is correct |
| 9 |
Correct |
6 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
604 KB |
Output is correct |
| 11 |
Correct |
2 ms |
604 KB |
Output is correct |
| 12 |
Correct |
5 ms |
604 KB |
Output is correct |
| 13 |
Correct |
55 ms |
344 KB |
Output is correct |
| 14 |
Runtime error |
356 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
280 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
424 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1112 KB |
Output is correct |
| 9 |
Correct |
6 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
604 KB |
Output is correct |
| 11 |
Correct |
2 ms |
604 KB |
Output is correct |
| 12 |
Correct |
5 ms |
604 KB |
Output is correct |
| 13 |
Correct |
55 ms |
344 KB |
Output is correct |
| 14 |
Runtime error |
356 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Halted |
0 ms |
0 KB |
- |
