oj.uz

Submission #652231

# Submission time Handle Problem Language Result Execution time Memory
652231 2022-10-21T18:31:01 Z ymm Lottery (CEOI18_lot) C++17
45 / 100
 3000 ms 32484 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace mmu {
	const int page_size = 128;
	const int page_cnt = 100000;
	short page[page_cnt][page_size];
	vector<int> free_pages;

	void init()
	{
		free_pages.resize(page_cnt);
		iota(free_pages.begin(), free_pages.end(), 0);
	}

	void free(short *p)
	{
		int i = (p - page[0]) / page_size;
		free_pages.push_back(i);
	}

	short *alloc()
	{
		if (free_pages.empty())
			return NULL;
		int ans = free_pages.back();
		free_pages.pop_back();
		return page[ans];
	}
}

struct list_node {
	short *page;
	int off;
	int nxt;
} list_pool[10000000];

int new_list_node()
{
	static int nxt = 1;
	return nxt++;
}

const int N = 10000;
const int Q = 100;
int mylist[N];
int n, q, l;

void pop_list(int i)
{
	mmu::free(list_pool[mylist[i]].page);
	mylist[i] = list_pool[mylist[i]].nxt;
}

short *list_page_alloc()
{
	static int p = 0;
	short *ans = mmu::alloc();
	if (ans) {
		return ans;
	} else {
		while (!mylist[p])
			++p;
		pop_list(p);
		return mmu::alloc();
	}
}

void make_list(int i)
{
	if (i % mmu::page_size == 0) {
		Loop (j,0,i) {
			if (mylist[j] && list_pool[mylist[j]].off < i)
				pop_list(j);
		}
	}
	mylist[i] = new_list_node();
	list_node *ls = &list_pool[mylist[i]];
	int off = i - i%mmu::page_size;
	for (;;) {
		ls->off = off;
		ls->page = list_page_alloc();
		off += mmu::page_size;
		if (off >= n-l+1)
			break;
		ls->nxt = new_list_node();
		ls = &list_pool[ls->nxt];
	}
}

short *get_from_list(int l, int i)
{
	if (!mylist[l])
		return NULL;
	list_node *p = &list_pool[mylist[l]];
	if (p->off > i)
		return NULL;
	return &p->page[i - p->off];
}

int noncmp_a[N];
short a[N];

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
short get_sim(int i, int j, int l)
{
	short ans = 0;
	for (int k = 0; k < l; ++k)
		ans += a[i+k] == a[j+k];
	return l-ans;
}
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
tuple<short,short,short> get_sim3(int i, int j0, int j1, int j2, int l)
{
	short ans0 = 0, ans1 = 0, ans2 = 0;
	for (int k = 0; k < l; ++k) {
		ans0 += a[i+k] == a[j0+k];
		ans1 += a[i+k] == a[j1+k];
		ans2 += a[i+k] == a[j2+k];
	}
	return {l-ans0, l-ans1, l-ans2};
}

short sim_cnt[N+1];
short sim_pre[N+2];
short ans[Q][N];
short query[Q];

short fail[N], fail_size;

void process(int i)
{
	memset(sim_cnt, 0, sizeof(sim_cnt));
	make_list(i);
	fail_size = 0;
	Loop (j,0,i) {
		short *x = get_from_list(j, i);
		if (x)
			sim_cnt[*x]++;
		else
			fail[fail_size++] = j;
	}
	for (int j = 0; j+3 <= fail_size; j += 3) {
		auto [x, y, z] = get_sim3(i, fail[j], fail[j+1], fail[j+2], l);
		sim_cnt[x]++;
		sim_cnt[y]++;
		sim_cnt[z]++;
	}
	for (int j = fail_size - fail_size%3; j < fail_size; ++j)
		sim_cnt[get_sim(i, fail[j], l)]++;
	list_node *ls = &list_pool[mylist[i]];
	short h3[3];
	Loop (j,i+1,n-l+1) {
		if (j%3 == (i+1)%3) {
			if (j+3 <= n-l+1) {
				auto tmp = get_sim3(i, j, j+1, j+2, l);
				tie(h3[0], h3[1], h3[2]) = tmp;
			} else {
				Loop (k,j,n-l+1)
					h3[k-j] = get_sim(i, k, l);
			}
		} else {
			h3[0] = h3[1];
			h3[1] = h3[2];
		}
		short x = h3[0];
		if (j >= ls->off + mmu::page_size)
			ls = &list_pool[ls->nxt];
		ls->page[j - ls->off] = x;
		sim_cnt[x]++;
	}
	sim_pre[0] = 0;
	Loop (j,0,l+1)
		sim_pre[j+1] = sim_pre[j] + sim_cnt[j];
	Loop (j,0,q)
		ans[j][i] = sim_pre[query[j]+1];
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	vector<int> cmper;
	cin >> n >> l;
	Loop (i,0,n) {
		cin >> noncmp_a[i];
		cmper.push_back(noncmp_a[i]);
	}
	cin >> q;
	Loop (i,0,q)
		cin >> query[i];
	sort(cmper.begin(), cmper.end());
	cmper.resize(unique(cmper.begin(), cmper.end()) - cmper.begin());
	Loop (i,0,n) {
		a[i] = lower_bound(cmper.begin(), cmper.end(),
		                   noncmp_a[i]) - cmper.begin();
	}
	mmu::init();
	Loop (i,0,n-l+1)
		process(i);
	Loop (i,0,q) {
		Loop (j,0,n-l+1)
			cout << ans[i][j] << ' ';
		cout << '\n';
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 832 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 832 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 51 ms 3412 KB Output is correct
14 Correct 67 ms 2232 KB Output is correct
15 Correct 63 ms 2124 KB Output is correct
16 Correct 64 ms 3012 KB Output is correct
17 Correct 70 ms 3000 KB Output is correct
18 Correct 71 ms 2988 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1970 ms 32484 KB Output is correct
2 Correct 2180 ms 32356 KB Output is correct
3 Correct 1799 ms 32412 KB Output is correct
4 Correct 2630 ms 32248 KB Output is correct
5 Execution timed out 3052 ms 15184 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1970 ms 32484 KB Output is correct
2 Correct 2180 ms 32356 KB Output is correct
3 Correct 1799 ms 32412 KB Output is correct
4 Correct 2630 ms 32248 KB Output is correct
5 Execution timed out 3052 ms 15184 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 864 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 832 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 3 ms 980 KB Output is correct
12 Correct 3 ms 980 KB Output is correct
13 Correct 51 ms 3412 KB Output is correct
14 Correct 67 ms 2232 KB Output is correct
15 Correct 63 ms 2124 KB Output is correct
16 Correct 64 ms 3012 KB Output is correct
17 Correct 70 ms 3000 KB Output is correct
18 Correct 71 ms 2988 KB Output is correct
19 Correct 1970 ms 32484 KB Output is correct
20 Correct 2180 ms 32356 KB Output is correct
21 Correct 1799 ms 32412 KB Output is correct
22 Correct 2630 ms 32248 KB Output is correct
23 Execution timed out 3052 ms 15184 KB Time limit exceeded
24 Halted 0 ms 0 KB -