Submission #467997

#	Time	Username	Problem	Language	Result	Execution time	Memory
467997		ivan_tudor	Lottery (CEOI18_lot)	C++14	0 / 100	484 ms	496 KiB

lot

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
int scor[2][N];
struct queryhelper{
  int id;
  int k;
};
short ans[101][N];
int v[N];
int l;
int getscor(int x, int y){
  int ans = 0;
  for(int i = 0; i < l; i++){
    if(v[x + i] != v[y + i])
      ans++;
  }
  return ans;
}
bool cmpl(queryhelper a, queryhelper b){
  return a.k < b.k;
}
int precalc[N];
queryhelper q[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, qs;
  cin>>n>>l;
  for(int i = 1; i<=n; i++)
    cin>>v[i];
  cin>>qs;
  for(int i =1 ; i<=qs; i++){
    int k;
    cin>>k;
    q[i] = {i, k};
  }
  sort(q +1, q+qs, cmpl);
  for(int i = 1; i <= qs; i++){
    if(precalc[q[i].k] == 0)
      precalc[q[i].k] = q[i].id;
  }
  for(int i = l; i >= 0; i--){
    if(precalc[i] == 0)
      precalc[i] = precalc[i + 1];
  }
  for(int i = 2; i <= n - l + 1; i++){
    scor[1][i] = getscor(1, i);
    int poz = precalc[scor[1][i]];
    ans[poz][1]++;
    ans[poz][i]++;
  }
  for(int i = 2; i <= n - l + 1; i++){
    int cur = i % 2, lst = 1 - cur;
    for(int j = i + 1; j <= n - l + 1; j++){
      scor[cur][j] = scor[lst][j - 1] - (v[i - 1] != v[j - 1]) + (v[i + l -1] != v[j + l - 1]);
      /// scor[i][j]
      int poz = precalc[scor[cur][j]];
      ans[poz][i]++;
      ans[poz][j]++;
    }
  }
  for(int i = 1; i <= qs ; i++){
    if(q[i].id)
      for(int j = 1; j <= n- l + 1; j++){
        ans[q[i].id][j]+= ans[q[i - 1].id][j];
      }
  }
  for(int i = 1; i <= qs; i++){
    for(int j = 1; j <= n- l + 1; j++)
      cout<<ans[i][j]<<" ";
    cout<<"\n";
  }
  return 0;
}

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