oj.uz

Submission #144188

# Submission time Handle Problem Language Result Execution time Memory
144188 2019-08-16T09:48:07 Z Swan Lottery (CEOI18_lot) C++14
45 / 100
 1584 ms 3600 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
using namespace std;

typedef long long ll;

vector<int> seq[400];
vector<int> v;
int n,l;
ll mod = 1e9+7;
ll pwr = 51;
ll pw[20000];
ll get_val[20000];
unordered_map<ll,int> cnt;

ll mul(ll a,ll b){
    a%=mod;
    b%=mod;
    return (a*b)%mod;
}

ll pl(ll a,ll b){
    return (a+b)%mod;
}

int val(vector<int>& a,vector<int>& b,int k){
    int res = 0;
    for(int i(0); i < a.size();i++){
        if(a[i]!=b[i])res++;
    }
    return res<=k;
}

void get_hash(vector<int>& v,int id){
    ll hs = 0;
    for(int i(0); i < v.size();i++){
        hs = pl(hs,mul(v[i],pw[i]));
    }
    get_val[id] = hs;
    cnt[hs]++;
}

void brute(){
    pw[0] = 1;
    for(int i(1); i < 20000;i++){
        pw[i] = mul(pw[i-1],pwr);
    }
    int q; cin >> q;
    if(q == 1){
        for(int i(0); i < n;i++){
            int r = i+l-1;
            vector<int> w;
            if(r>=n)break;
            for(int j(i);j<=r;j++){
                w.push_back(v[j]);
            }
            get_hash(w,i);
        }
        int k; cin >> k;
        if(k == 0){
            for(int i(0); i < n-l+1;i++)cout << cnt[get_val[i]]-1 << ' ';
            exit(0);
        }
    }
    for(int i(0); i < n;i++){
        int r = i+l-1;
        if(r >= n)break;
        for(int j(i);j<=r;j++){
            seq[i].push_back(v[j]);
        }
        get_hash(seq[i],i);
    }

    for(int i(0); i < q;i++){
        int k; cin >> k;
        for(int j(0); j < n-l+1;j++){
            int ans = 0;
            for(int z(0); z < n-l+1;z++){
                if(j == z)continue;
                ans+=val(seq[j],seq[z],k);
            }
            cout << ans << ' ';
        }
        cout << '\n';
    }
}

main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> l;
    for(int i(0); i < n;i++){
        int x; cin >> x;
        v.push_back(x);
    }
    brute();
    return 0;
}
/*
6 2
1 2 1 3 2 1
1
0
*/

Compilation message

lot.cpp: In function 'int val(std::vector<int>&, std::vector<int>&, int)':
lot.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < a.size();i++){
                   ~~^~~~~~~~~~
lot.cpp: In function 'void get_hash(std::vector<int>&, int)':
lot.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
lot.cpp: At global scope:
lot.cpp:90:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 74 ms 760 KB Output is correct
9 Correct 74 ms 712 KB Output is correct
10 Correct 36 ms 636 KB Output is correct
11 Correct 31 ms 504 KB Output is correct
12 Correct 55 ms 632 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 74 ms 760 KB Output is correct
9 Correct 74 ms 712 KB Output is correct
10 Correct 36 ms 636 KB Output is correct
11 Correct 31 ms 504 KB Output is correct
12 Correct 55 ms 632 KB Output is correct
13 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 760 KB Output is correct
2 Correct 10 ms 760 KB Output is correct
3 Correct 9 ms 760 KB Output is correct
4 Correct 135 ms 960 KB Output is correct
5 Correct 1560 ms 1256 KB Output is correct
6 Correct 423 ms 1144 KB Output is correct
7 Correct 1577 ms 1016 KB Output is correct
8 Correct 1324 ms 888 KB Output is correct
9 Correct 214 ms 988 KB Output is correct
10 Correct 134 ms 888 KB Output is correct
11 Correct 128 ms 672 KB Output is correct
12 Correct 892 ms 1144 KB Output is correct
13 Correct 1505 ms 1288 KB Output is correct
14 Correct 1584 ms 1156 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 760 KB Output is correct
2 Correct 10 ms 760 KB Output is correct
3 Correct 9 ms 760 KB Output is correct
4 Correct 135 ms 960 KB Output is correct
5 Correct 1560 ms 1256 KB Output is correct
6 Correct 423 ms 1144 KB Output is correct
7 Correct 1577 ms 1016 KB Output is correct
8 Correct 1324 ms 888 KB Output is correct
9 Correct 214 ms 988 KB Output is correct
10 Correct 134 ms 888 KB Output is correct
11 Correct 128 ms 672 KB Output is correct
12 Correct 892 ms 1144 KB Output is correct
13 Correct 1505 ms 1288 KB Output is correct
14 Correct 1584 ms 1156 KB Output is correct
15 Runtime error 222 ms 3600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 74 ms 760 KB Output is correct
9 Correct 74 ms 712 KB Output is correct
10 Correct 36 ms 636 KB Output is correct
11 Correct 31 ms 504 KB Output is correct
12 Correct 55 ms 632 KB Output is correct
13 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -