#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_1-hash[i-1]+MOD)%MOD;
if (j>0) hash_2 = (hash_2-hash[j-1]+MOD)%MOD;
//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;
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
1112 KB |
Output is correct |
9 |
Correct |
5 ms |
824 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
600 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
1112 KB |
Output is correct |
9 |
Correct |
5 ms |
824 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
600 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
13 |
Correct |
56 ms |
552 KB |
Output is correct |
14 |
Runtime error |
373 ms |
65536 KB |
Execution killed with signal 9 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
564 ms |
548 KB |
Output is correct |
2 |
Correct |
579 ms |
544 KB |
Output is correct |
3 |
Correct |
568 ms |
544 KB |
Output is correct |
4 |
Correct |
544 ms |
348 KB |
Output is correct |
5 |
Correct |
191 ms |
528 KB |
Output is correct |
6 |
Correct |
507 ms |
560 KB |
Output is correct |
7 |
Correct |
143 ms |
348 KB |
Output is correct |
8 |
Correct |
274 ms |
532 KB |
Output is correct |
9 |
Correct |
519 ms |
544 KB |
Output is correct |
10 |
Correct |
576 ms |
532 KB |
Output is correct |
11 |
Correct |
25 ms |
348 KB |
Output is correct |
12 |
Correct |
308 ms |
704 KB |
Output is correct |
13 |
Correct |
199 ms |
600 KB |
Output is correct |
14 |
Correct |
214 ms |
616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
564 ms |
548 KB |
Output is correct |
2 |
Correct |
579 ms |
544 KB |
Output is correct |
3 |
Correct |
568 ms |
544 KB |
Output is correct |
4 |
Correct |
544 ms |
348 KB |
Output is correct |
5 |
Correct |
191 ms |
528 KB |
Output is correct |
6 |
Correct |
507 ms |
560 KB |
Output is correct |
7 |
Correct |
143 ms |
348 KB |
Output is correct |
8 |
Correct |
274 ms |
532 KB |
Output is correct |
9 |
Correct |
519 ms |
544 KB |
Output is correct |
10 |
Correct |
576 ms |
532 KB |
Output is correct |
11 |
Correct |
25 ms |
348 KB |
Output is correct |
12 |
Correct |
308 ms |
704 KB |
Output is correct |
13 |
Correct |
199 ms |
600 KB |
Output is correct |
14 |
Correct |
214 ms |
616 KB |
Output is correct |
15 |
Execution timed out |
3070 ms |
27988 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 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 |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
8 ms |
1112 KB |
Output is correct |
9 |
Correct |
5 ms |
824 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
4 ms |
600 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
13 |
Correct |
56 ms |
552 KB |
Output is correct |
14 |
Runtime error |
373 ms |
65536 KB |
Execution killed with signal 9 |
15 |
Halted |
0 ms |
0 KB |
- |