oj.uz

Submission #652205

# Submission time Handle Problem Language Result Execution time Memory
652205 2022-10-21T17:05:08 Z ymm Lottery (CEOI18_lot) C++17
45 / 100
 3000 ms 32592 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)
{
	int _p1 = mmu::free_pages.size();
	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];
	}
	int _p2 = mmu::free_pages.size();
}

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];

void process(int i)
{
	memset(sim_cnt, 0, sizeof(sim_cnt));
	make_list(i);
	Loop (j,0,i) {
		short *x = get_from_list(j, i);
		if (x)
			sim_cnt[*x]++;
		else
			sim_cnt[get_sim(i, 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';
	}
}

Compilation message

lot.cpp: In function 'void make_list(int)':
lot.cpp:76:6: warning: unused variable '_p1' [-Wunused-variable]
   76 |  int _p1 = mmu::free_pages.size();
      |      ^~~
lot.cpp:95:6: warning: unused variable '_p2' [-Wunused-variable]
   95 |  int _p2 = mmu::free_pages.size();
      |      ^~~

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 848 KB Output is correct
3 Correct 1 ms 852 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 728 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 3 ms 984 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 848 KB Output is correct
3 Correct 1 ms 852 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 728 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 3 ms 984 KB Output is correct
13 Correct 47 ms 3356 KB Output is correct
14 Correct 65 ms 2192 KB Output is correct
15 Correct 62 ms 2176 KB Output is correct
16 Correct 66 ms 3052 KB Output is correct
17 Correct 66 ms 2948 KB Output is correct
18 Correct 65 ms 3020 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 32436 KB Output is correct
2 Correct 1773 ms 32332 KB Output is correct
3 Correct 1657 ms 32592 KB Output is correct
4 Correct 2626 ms 32444 KB Output is correct
5 Execution timed out 3065 ms 15672 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 32436 KB Output is correct
2 Correct 1773 ms 32332 KB Output is correct
3 Correct 1657 ms 32592 KB Output is correct
4 Correct 2626 ms 32444 KB Output is correct
5 Execution timed out 3065 ms 15672 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 848 KB Output is correct
3 Correct 1 ms 852 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 728 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 3 ms 984 KB Output is correct
13 Correct 47 ms 3356 KB Output is correct
14 Correct 65 ms 2192 KB Output is correct
15 Correct 62 ms 2176 KB Output is correct
16 Correct 66 ms 3052 KB Output is correct
17 Correct 66 ms 2948 KB Output is correct
18 Correct 65 ms 3020 KB Output is correct
19 Correct 1690 ms 32436 KB Output is correct
20 Correct 1773 ms 32332 KB Output is correct
21 Correct 1657 ms 32592 KB Output is correct
22 Correct 2626 ms 32444 KB Output is correct
23 Execution timed out 3065 ms 15672 KB Time limit exceeded
24 Halted 0 ms 0 KB -