Submission #82330

#	Time	Username	Problem	Language	Result	Execution time	Memory
82330		wzy	Lottery (CEOI18_lot)	C++11	100 / 100	1488 ms	11080 KiB

lot

/*
  Fix one diagonal and use prefix sum of a boolean matrix such that the position (i,j) represents mismatch of i and j
  is better to code if the diagonal is (i , 1) - > (i+1 , 2) -> (i+2 , 3) ... 

*/

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>

int n , l , q , a[10002] , k[101] , v[10002], r[10002][101] , pos[10002] , ans[10002][101], k2[101];

int32_t main(){
	scanf("%d%d" , &n , &l);
	for(int i = 1 ; i <= n;i ++) scanf("%d" ,  &a[i]);
	scanf("%d" , &q);
	for(int i = 1 ; i <= q ;i ++) scanf("%d" , &k[i]), k2[i] = k[i];
	sort(k + 1 , k + 1 + q);
	for(int i = 1 ; i <= q; i ++) pos[k[i]] = i;
	// fix the diagonal
	v[0] = 0;
	for(int i = 1 ; i <= n; i ++){
		pii curr = pii(i, 1);
		int sz = 0;
		while(curr.F <= n && curr.S <= n){
			v[++sz] = (a[curr.F] != a[curr.S]);
			curr.F++ , curr.S++; 
		}
		curr = pii(i ,1);
		for(int j = 1 ; j <= sz; j++){
			v[j] += v[j-1];
		}
		for(int j = 1 ; j <= sz ;j ++){
			if(j>= l){
				pii cc = pii(i+j-1 , j);
				int U = v[j]-v[j-l];
				if(cc.F - l +1 == cc.S - l + 1) continue;
				int L = 1 , R = q;
				int ansj = -1;
				while(L<=R){
					int mid = (L + R)/2;
					if(k[mid] >= U){
						ansj = mid;
						R = mid - 1;
					}
					else L = mid + 1;
				}
				//cout<<cc.F - l + 1 <<" " << cc.S - l + 1 <<" " << U << " "<<ansj << " " << k[ansj] << endl;
				if(ansj != -1){
					r[cc.F - l + 1][ansj]++;
					r[cc.S - l + 1][ansj]++;
				}
			}
		}
	}
	for(int i = 1 ; i<= n; i ++){
		for(int j = 1 ; j <= q;j++){
			r[i][j] += r[i][j-1];
		}
	}	
	for(int j = 1 ; j <= q; j ++){
		for(int i = 1 ; i <= n-l+1;i ++){
			printf("%d ", r[i][pos[k2[j]]]);
		}
		printf("\n");
	}
}

Compilation message (stderr)

lot.cpp: In function 'int32_t main()':
lot.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n , &l);
  ~~~~~^~~~~~~~~~~~~~~~~~
lot.cpp:19:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i <= n;i ++) scanf("%d" ,  &a[i]);
                               ~~~~~^~~~~~~~~~~~~~~
lot.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &q);
  ~~~~~^~~~~~~~~~~
lot.cpp:21:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1 ; i <= q ;i ++) scanf("%d" , &k[i]), k2[i] = k[i];
                                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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