Submission #518483

#	Time	Username	Problem	Language	Result	Execution time	Memory
518483		Yazan_Alattar	Lottery (CEOI18_lot)	C++14	0 / 100	3 ms	592 KiB

lot

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 307;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct Hash1 {
	ll SEED = 1e9 + 1;//or 1333
	ll MOD = 1000000007;// or 1e9+9
	vector<ll> ha;
	vector<ll> power;
	void build(vector <int> x) {
        power.resize(x.size());
        ha.resize(x.size());
		power[0] = 1;
		for(int i=1; i<(int)power.size(); i++) power[i] = (power[i-1] * SEED)%MOD;
		ha[0] = x[0];
		for(int i=1; i<(int)ha.size(); i++) ha[i] = (ha[i-1] * SEED + x[i])%MOD;
	}

	void Add(vector <int> x)
	{
	    for(int i = 0; i < x.size(); i++)   power.push_back((power.back() * SEED)%MOD);
        for(int i = 0; i < x.size(); i++)   ha.push_back((ha.back() * SEED + x[i])%MOD);
	}

	//i,j inclusive
	ll get(int i, int j) {
		ll ret = ha[j];
		if (i) ret -= ha[i-1] * power[j - i + 1];
		ret = (ret % MOD + MOD) % MOD;
		return ret;
	}
}H;


int n, l, q;
map <int,int> cnt;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> l;
    vector <int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    H.build(a);
    for(int i = 0; i + l - 1 < n; ++i) ++cnt[H.get(i, i + l - 1)];
    cin >> q;
    while(q--){
        int k;
        cin >> k;
        for(int i = 0; i < n - l + 1; ++i) cout << cnt[H.get(i, i + l - 1)] - 1 << " ";
        cout << endl;
    }
    return 0;
}

Compilation message (stderr)

lot.cpp: In member function 'void Hash1::Add(std::vector<int>)':
lot.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |      for(int i = 0; i < x.size(); i++)   power.push_back((power.back() * SEED)%MOD);
      |                     ~~^~~~~~~~~~
lot.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0; i < x.size(); i++)   ha.push_back((ha.back() * SEED + x[i])%MOD);
      |                        ~~^~~~~~~~~~

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