oj.uz

Submission #1060184

# Submission time Handle Problem Language Result Execution time Memory
1060184 2024-08-15T11:22:13 Z SzymonKrzywda Lottery (CEOI18_lot) C++17
45 / 100
 3000 ms 65536 KB 
#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;
      |                 ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory 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

Subtask #2
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #4
0 / 15.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 -