Submission #397139

#	Time	Username	Problem	Language	Result	Execution time	Memory
397139		ollel	Lottery (CEOI18_lot)	C++17	25 / 100	3065 ms	65540 KiB

lot

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

int n, l;
vi arr;
vvi ksim;
vvi difs;

void precomp()
{
  rep(seq,0,n-l+1) {
    rep(i,0,l) {
      rep(seq2, 0, n-l+1) {
        if (seq == seq2) continue;
        if (arr[seq + i] != arr[seq2 + i]) difs[seq][seq2]++;
      }
    }
  }

  rep(i, 0, n-l+1) {
    rep(j, 0, n-l+1) {
      if (i == j) continue;
      ksim[i].pb(difs[i][j]);
    }
  }
  rep(i,0,n-l+1) sort(ksim[i].begin(), ksim[i].end());
}

int main()
{
  cin>>n>>l;
  arr.resize(n);
  rep(i,0,n) cin>>arr[i];
  difs.resize(n); rep(i,0,n-l+1) difs[i].assign(n-l+1, 0);
  ksim.resize(n);

  precomp();

  int q, k;
  cin >> q;
  rep(i,0,q) {
    cin >> k;
    rep(i, 0, n-l+1) {
      int x = upper_bound(ksim[i].begin(), ksim[i].end(), k) - ksim[i].begin();
      cout << x << " ";
    }
    cout << endl;
  }

}

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