Submission #72907

#	Time	Username	Problem	Language	Result	Execution time	Memory
72907		duckmoon99	Lottery (CEOI18_lot)	C++14	25 / 100	123 ms	2076 KiB

lot

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[11111];
map <deque<int>, set<int> > mm;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, l, k;
    cin >> n >> l;
    for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	int q;
	cin >> q;
	if(n<=300){
	while(q--){
		cin >> k;
		for(int i = 0; i < n-l+1; i++){
			int ans = 0;
			for(int j = 0; j < n-l+1; j++){
				if(i!=j){
					int cnt = 0;
					for(int m = 0; m < l; m++){
						if(a[i+m]==a[j+m]){
							cnt++;
						}
					}
					if(cnt>=l-k)ans++;
				}
			}
			cout << ans << " ";
		}
		cout << '\n';
	}
	}
	else{
		cin >> k;
		deque <int> q;
		for(int i = 0; i < l; i++){
			q.pb(a[i]);
		}
		mm[q].insert(0);
		for(int i = l; i < n; i++){
			q.pb(a[i]);
			q.pop_front();
			mm[q].insert(i-l+1);
		}
		int ans[11111];
		for(auto it: mm){
			for(auto itt: it.se){
				ans[itt]=it.se.size();
			}
		}
		for(int i = 0; i < n-l+1; i++){
			cout << ans[i] << " ";
		}
		
	}
	
}

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