Submission #855212

#	Time	Username	Problem	Language	Result	Execution time	Memory
855212		lovrot	Lottery (CEOI18_lot)	C++17	100 / 100	324 ms	8784 KiB

lot

#include <cstdio>
#include <vector>
#include <algorithm> 

#define EB emplace_back

using namespace std; 

const int N = 1e4 + 10; 
const int M = 110;

int n, q, A[N], B[N], l;

int Q[N];
int CNT[N][M]; 
vector<int> S;

void count(int a, int b) {
	if(a == b) return;
	int nim = -(a < b ? a : b);
	a += nim;
	b += nim; 
	
	int diff = 0;
	for(int i = 0; a + i < n && b + i < n; ++i) {
		diff += A[a + i] != A[b + i];
		if(a + i - l >= 0 && b + i - l >= 0) diff -= A[b + i - l] != A[a + i - l];
		if(a + i - l + 1 >= 0 && b + i - l + 1 >= 0) {
			++CNT[a + i - l + 1][Q[diff]];
			++CNT[b + i - l + 1][Q[diff]];
		}
	}
}

int main() {
	scanf("%d%d", &n, &l);
	for(int i = 0; i < n; ++i) scanf("%d", A + i); 
	scanf("%d", &q);
	for(int i = 0; i < q; ++i) {	
		scanf("%d", B + i); 
		S.EB(B[i]); 
	}
	sort(S.begin(), S.end());
	S.erase(unique(S.begin(), S.end()), S.end());
	for(int i = l, j = S.size(); i >= 0; --i) {
		if(j && i == S[j - 1]) --j;
		Q[i] = j;
	}
	for(int i = n - l; i >= 0; --i) count(i, 0); 
	for(int i = 0; i < n - l + 1; ++i) 
		for(int j = 1; j < S.size(); ++j) CNT[i][j] += CNT[i][j - 1];
	for(int i = 0; i < q; ++i) 
		for(int j = 0; j < n - l + 1; ++j) printf("%d%c", CNT[j][Q[B[i]]], " \n"[j == n - l]);
	return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j = 1; j < S.size(); ++j) CNT[i][j] += CNT[i][j - 1];
      |                  ~~^~~~~~~~~~
lot.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d%d", &n, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:37:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  for(int i = 0; i < n; ++i) scanf("%d", A + i);
      |                             ~~~~~^~~~~~~~~~~~~
lot.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
lot.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", B + i);
      |   ~~~~~^~~~~~~~~~~~~

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