Submission #144154

#	Time	Username	Problem	Language	Result	Execution time	Memory
144154		Swan	Lottery (CEOI18_lot)	C++14	25 / 100	75 ms	760 KiB

lot

#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;
int mod = 1e9+7;
int pwr = 51;
long long pw[20000];
int get_val[20000];
unordered_map<int,int> cnt;

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

ll pl(int a,int 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);
    }
    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);
    }
    int q; cin >> q;
    if(q == 1){
        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 < 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);
    }
    if(n<=300)brute();
    return 0;
}
/*
8 2
1 2 3 1 3 1 2 3
1
0
*/

Compilation message (stderr)

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:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20