Submission #77956

#	Time	Username	Problem	Language	Result	Execution time	Memory
77956		Saboon	Lottery (CEOI18_lot)	C++14	100 / 100	680 ms	15952 KiB

lot

#include <iostream>
#include <queue>
#include <stack>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <cmath>
#include <cassert>
#include <unordered_set>
#include <map>
#include <deque>
#include <unordered_map>
#include <fstream>
#include <set>
#include <algorithm>
#include <iomanip>
#define fin cin
#define fout cout
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int maxn = 10000 + 10;

int a[maxn], nex[maxn], dp[maxn][110];
pii q[maxn];
vector <int> v[maxn];

int n, l;

int similar (int fi, int se) {
    int ret = 0;
    for (int x = 0; x < l; x++)
        ret += (a[fi + x] != a[se + x]);
    return ret;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin >> n >> l;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> q[i].F;
        q[i].S = i;
    }
    sort (q, q + Q);
    for (int i = l; i >= 0; i--) {
        nex[i] = lower_bound (q, q + Q, MP (i, 0)) - q;
    }
    for (int dis = 1; dis < n - l + 1; dis++) {
        int cnt = similar (0, dis);
        dp[0][nex[cnt]] ++;
        dp[dis][nex[cnt]] ++;
        for (int i = 0; i < n - l - dis; i++) {
            cnt -= (a[i] != a[(i + dis) % n]);
            cnt += (a[i + l] != a[i + dis + l]);
            dp[i + 1][nex[cnt]] ++;
            dp[i + dis + 1][nex[cnt]] ++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < Q - 1; j++) {
            dp[i][j + 1] += dp[i][j];
        }
    }
    for (int i = 0; i < Q; i++) {
        for (int j = 0; j < n - l + 1; j++) {
            v[q[i].S].PB (dp[j][i]);
        }
    }
    for (int j = 0; j < Q; j++) {
        for (auto w : v[j])
            cout << w << " ";
        cout << endl;
    }
}

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