QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#404416	#2759. The Big Prize	5ab	100 ✓	22ms	4896kb	C++20	2.4kb	2024-05-03 22:03:21	2024-05-03 22:03:22

Judging History

This is the latest submission verdict.

[2024-05-03 22:03:22]
Judged

Verdict: 100
Time: 22ms
Memory: 4896kb

Show

[2024-05-03 22:03:21]
Submitted

answer

/* name: prize
 * author: 5ab
 * created at: 2024-05-03
 */
#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 2e5;

int mn[N + 1];
vector<int> ps, nps;

void solve(int l, int r, int sv, int ev, int gc) // [l, r)
{
	// cerr << l << " " << r << " " << sv << " " << ev << endl;
	if (l >= r)
		return;
	if (sv == ev)
		return;
	if (ev - sv == r - l)
	{
		for (int i = l; i < r; i++)
			nps.push_back(ps[i]);
		return;
	}
	int mid = (l + r + 1) >> 1, lm = mid, mc = 0, xq = sv;
	while (lm > l)
	{
		auto _ = ask(ps[lm - 1]);
		auto x = _[0], y = _[1];
		if (x + y == gc)
		{
			xq = x;
			break;
		}
		mc++, lm--;
	}
	solve(l, lm - 1, sv, xq, gc);
	for (int i = lm; i < mid; i++)
		nps.push_back(ps[i]);
	solve(mid, r, xq + mc, ev, gc);
}

int find_best(int n)
{
	fill(mn + 1, mn + N + 1, N);
	for (int i = 1; i <= N; i++)
	{
		chmin(mn[i], mn[i - 1] + 1);
		if (1ll * mn[i] * mn[i] + 1 + i <= N)
			chmin(mn[mn[i] * mn[i] + 1 + i], mn[i] * mn[i] + 1);
	}
	// for (int x = N; x > 1; x -= mn[x])
	// 	cerr << x << endl;
	ps.resize(n);
	iota(all(ps), 0);
	while (ssz(ps) > 1)
	{
		// cerr << ssz(ps) << "   ";
		// for (int x : ps)
		// 	cerr << x << " ";
		// cerr << endl;
		// cerr << ssz(ps) - mn[ssz(ps)] << endl;
		vector<pair<int, int>> tmp;
		
		int cc = min(ssz(ps) - 1, ssz(ps) - mn[ssz(ps)] + 1), cnt = -1;
		for (int i = 1; i <= cc; i++)
		{
			int x = ssz(ps) * i / (cc + 1);
			auto v = ask(ps[x]);
			chmax(cnt, v[0] + v[1]);
			tmp.emplace_back(v[0], v[1]);
		}
		// cerr << "ok" << endl;
		nps.clear();
		for (int i = 0, ls = 0; i <= cc; i++)
		{
			int x = ssz(ps) * i / (cc + 1) + (i != 0), y = ssz(ps) * (i + 1) / (cc + 1), cm = 0, nx, ry = y;
			if (i != cc)
			{
				int cx, cy;
				tie(cx, cy) = tmp[i];
				// cerr << y << endl;
				while (cx + cy != cnt)
				{
					cm++, y--;
					if (x > y) break;
					auto _ = ask(ps[y]);
					cx = _[0], cy = _[1];
				}
				nx = cx;
			}
			else
				nx = cnt;
			solve(x, y, ls, nx, cnt);
			// cerr << x << " " << y << endl;
			for (int j = y + 1; j <= ry; j++)
				nps.push_back(ps[j]);
			ls = nx + cm;
		}
		swap(ps, nps);
	}
	return ps[0];
}
// started coding at: 05-03 19:25:17

源文件, 语言: C++20

详细

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 2ms

memory: 4696kb

input:

output:

result:

ok

Test #2:

score: 20

Accepted

time: 0ms

memory: 4736kb

input:

output:

result:

ok

Test #3:

score: 20

Accepted

time: 4ms

memory: 4664kb

input:

output:

result:

ok

Test #4:

score: 20

Accepted

time: 0ms

memory: 4892kb

input:

output:

result:

ok

Test #5:

score: 20

Accepted

time: 0ms

memory: 4620kb

input:

output:

result:

ok

Test #6:

score: 20

Accepted

time: 4ms

memory: 4700kb

input:

output:

result:

ok

Test #7:

score: 20

Accepted

time: 0ms

memory: 4892kb

input:

output:

result:

ok

Test #8:

score: 20

Accepted

time: 2ms

memory: 4816kb

input:

output:

result:

ok

Test #9:

score: 20

Accepted

time: 0ms

memory: 4740kb

input:

output:

result:

ok

Test #10:

score: 20

Accepted

time: 2ms

memory: 4828kb

input:

output:

result:

ok

Subtask #2:

score: 80

Accepted

Test #11:

score: 80

Accepted

time: 4ms

memory: 4828kb

input:

output:

result:

ok

Test #12:

score: 80

Accepted

time: 4ms

memory: 4892kb

input:

output:

result:

ok

Test #13:

score: 80

Accepted

time: 2ms

memory: 4736kb

input:

output:

result:

ok

Test #14:

score: 80

Accepted

time: 2ms

memory: 4628kb

input:

output:

result:

ok

Test #15:

score: 80

Accepted

time: 5ms

memory: 4684kb

input:

output:

result:

ok

Test #16:

score: 80

Accepted

time: 0ms

memory: 4656kb

input:

output:

result:

ok

Test #17:

score: 80

Accepted

time: 4ms

memory: 4896kb

input:

output:

result:

ok

Test #18:

score: 80

Accepted

time: 0ms

memory: 4696kb

input:

output:

result:

ok

Test #19:

score: 80

Accepted

time: 0ms

memory: 4740kb

input:

output:

result:

ok

Test #20:

score: 80

Accepted

time: 4ms

memory: 4732kb

input:

output:

result:

ok

Test #21:

score: 80

Accepted

time: 0ms

memory: 4624kb

input:

output:

result:

ok

Test #22:

score: 80

Accepted

time: 0ms

memory: 4692kb

input:

output:

result:

ok

Test #23:

score: 80

Accepted

time: 6ms

memory: 4664kb

input:

output:

result:

ok

Test #24:

score: 80

Accepted

time: 3ms

memory: 4836kb

input:

output:

result:

ok

Test #25:

score: 80

Accepted

time: 0ms

memory: 4664kb

input:

output:

result:

ok

Test #26:

score: 80

Accepted

time: 6ms

memory: 4684kb

input:

output:

result:

ok

Test #27:

score: 80

Accepted

time: 3ms

memory: 4736kb

input:

output:

result:

ok

Test #28:

score: 80

Accepted

time: 6ms

memory: 4672kb

input:

output:

result:

ok

Test #29:

score: 80

Accepted

time: 5ms

memory: 4616kb

input:

output:

result:

ok

Test #30:

score: 80

Accepted

time: 5ms

memory: 4764kb

input:

output:

result:

ok

Test #31:

score: 80

Accepted

time: 6ms

memory: 4748kb

input:

output:

result:

ok

Test #32:

score: 80

Accepted

time: 0ms

memory: 4700kb

input:

output:

result:

ok

Test #33:

score: 80

Accepted

time: 5ms

memory: 4728kb

input:

output:

result:

ok

Test #34:

score: 80

Accepted

time: 6ms

memory: 4752kb

input:

output:

result:

ok

Test #35:

score: 80

Accepted

time: 0ms

memory: 4744kb

input:

output:

result:

ok

Test #36:

score: 80

Accepted

time: 5ms

memory: 4752kb

input:

output:

result:

ok

Test #37:

score: 80

Accepted

time: 0ms

memory: 4832kb

input:

output:

result:

ok

Test #38:

score: 80

Accepted

time: 5ms

memory: 4760kb

input:

output:

result:

ok

Test #39:

score: 80

Accepted

time: 5ms

memory: 4652kb

input:

output:

result:

ok

Test #40:

score: 80

Accepted

time: 7ms

memory: 4888kb

input:

output:

result:

ok

Test #41:

score: 80

Accepted

time: 5ms

memory: 4760kb

input:

output:

result:

ok

Test #42:

score: 80

Accepted

time: 6ms

memory: 4672kb

input:

output:

result:

ok

Test #43:

score: 80

Accepted

time: 1ms

memory: 4776kb

input:

output:

A 7
A 14
A 21
A 28
A 35
A 42
A 50
A 57
A 64
A 71
A 78
A 85
A 92
A 6
A 5
A 2
A 46
A 44
A 43
A 67
A 65
A 69
A 68
A 77
A 91
A 88
A 89
A 96
A 94
A 98
A 97
A 6
A 44
A 78
A 92
A 4
A 65
A 6
A 69
B 3

result:

ok

Test #44:

score: 80

Accepted

time: 12ms

memory: 4744kb

input:

output:

result:

ok

Test #45:

score: 80

Accepted

time: 0ms

memory: 4828kb

input:

output:

result:

ok

Test #46:

score: 80

Accepted

time: 6ms

memory: 4816kb

input:

output:

result:

ok

Test #47:

score: 80

Accepted

time: 3ms

memory: 4660kb

input:

output:

result:

ok

Test #48:

score: 80

Accepted

time: 5ms

memory: 4632kb

input:

output:

result:

ok

Test #49:

score: 80

Accepted

time: 11ms

memory: 4832kb

input:

output:

result:

ok

Test #50:

score: 80

Accepted

time: 0ms

memory: 4732kb

input:

output:

result:

ok

Test #51:

score: 80

Accepted

time: 0ms

memory: 4748kb

input:

output:

result:

ok

Test #52:

score: 80

Accepted

time: 6ms

memory: 4756kb

input:

output:

result:

ok

Test #53:

score: 80

Accepted

time: 0ms

memory: 4668kb

input:

output:

result:

ok

Test #54:

score: 80

Accepted

time: 4ms

memory: 4676kb

input:

output:

result:

ok

Test #55:

score: 80

Accepted

time: 3ms

memory: 4632kb

input:

output:

result:

ok

Test #56:

score: 80

Accepted

time: 0ms

memory: 4624kb

input:

output:

result:

ok

Test #57:

score: 80

Accepted

time: 0ms

memory: 4744kb

input:

output:

result:

ok

Test #58:

score: 80

Accepted

time: 12ms

memory: 4664kb

input:

output:

result:

ok

Test #59:

score: 80

Accepted

time: 0ms

memory: 4732kb

input:

output:

result:

ok

Test #60:

score: 80

Accepted

time: 0ms

memory: 4656kb

input:

output:

result:

ok

Test #61:

score: 80

Accepted

time: 14ms

memory: 4620kb

input:

output:

result:

ok

Test #62:

score: 80

Accepted

time: 8ms

memory: 4624kb

input:

output:

result:

ok

Test #63:

score: 80

Accepted

time: 4ms

memory: 4664kb

input:

output:

result:

ok

Test #64:

score: 80

Accepted

time: 6ms

memory: 4760kb

input:

output:

result:

ok

Test #65:

score: 80

Accepted

time: 6ms

memory: 4740kb

input:

output:

result:

ok

Test #66:

score: 80

Accepted

time: 4ms

memory: 4628kb

input:

output:

result:

ok

Test #67:

score: 80

Accepted

time: 10ms

memory: 4736kb

input:

output:

result:

ok

Test #68:

score: 80

Accepted

time: 12ms

memory: 4680kb

input:

output:

result:

ok

Test #69:

score: 80

Accepted

time: 5ms

memory: 4756kb

input:

output:

result:

ok

Test #70:

score: 80

Accepted

time: 22ms

memory: 4740kb

input:

output:

result:

ok

Test #71:

score: 80

Accepted

time: 0ms

memory: 4816kb

input:

output:

result:

ok

Test #72:

score: 80

Accepted

time: 0ms

memory: 4736kb

input:

output:

result:

ok

Test #73:

score: 80

Accepted

time: 0ms

memory: 4812kb

input:

output:

result:

ok

Test #74:

score: 80

Accepted

time: 6ms

memory: 4656kb

input:

output:

result:

ok

Test #75:

score: 80

Accepted

time: 3ms

memory: 4812kb

input:

output:

result:

ok

Test #76:

score: 80

Accepted

time: 0ms

memory: 4628kb

input:

output:

result:

ok

Test #77:

score: 80

Accepted

time: 4ms

memory: 4620kb

input:

output:

result:

ok

Test #78:

score: 80

Accepted

time: 3ms

memory: 4752kb

input:

output:

result:

ok

Test #79:

score: 80

Accepted

time: 5ms

memory: 4624kb

input:

output:

result:

ok

Test #80:

score: 80

Accepted

time: 0ms

memory: 4664kb

input:

output:

result:

ok

Test #81:

score: 80

Accepted

time: 4ms

memory: 4764kb

input:

output:

result:

ok

Test #82:

score: 80

Accepted

time: 3ms

memory: 4888kb

input:

output:

result:

ok

Test #83:

score: 80

Accepted

time: 5ms

memory: 4616kb

input:

output:

result:

ok

Test #84:

score: 80

Accepted

time: 12ms

memory: 4672kb

input:

output:

result:

ok

Test #85:

score: 80

Accepted

time: 6ms

memory: 4668kb

input:

output:

result:

ok

Test #86:

score: 80

Accepted

time: 0ms

memory: 4628kb

input:

output:

result:

ok

Test #87:

score: 80

Accepted

time: 0ms

memory: 4656kb

input:

output:

result:

ok

Test #88:

score: 80

Accepted

time: 0ms

memory: 4632kb

input:

output:

result:

ok

Test #89:

score: 80

Accepted

time: 2ms

memory: 4832kb

input:

output:

result:

ok

Test #90:

score: 80

Accepted

time: 0ms

memory: 4828kb

input:

output:

result:

ok

Test #91:

score: 80

Accepted

time: 14ms

memory: 4648kb

input:

output:

result:

ok

Test #92:

score: 80

Accepted

time: 6ms

memory: 4624kb

input:

output:

result:

ok

Test #93:

score: 80

Accepted

time: 0ms

memory: 4656kb

input:

output:

result:

ok

Test #94:

score: 80

Accepted

time: 0ms

memory: 4736kb

input:

output:

result:

ok

Test #95:

score: 80

Accepted

time: 20ms

memory: 4656kb

input:

output:

result:

ok

Test #96:

score: 80

Accepted

time: 3ms

memory: 4740kb

input:

output:

result:

ok

Test #97:

score: 80

Accepted

time: 0ms

memory: 4892kb

input:

output:

result:

ok

Test #98:

score: 80

Accepted

time: 3ms

memory: 4652kb

input:

output:

result:

ok

Test #99:

score: 80

Accepted

time: 4ms

memory: 4896kb

input:

output:

result:

ok

Test #100:

score: 80

Accepted

time: 0ms

memory: 4620kb

input:

output:

result:

ok

Test #101:

score: 80

Accepted

time: 6ms

memory: 4656kb

input:

output:

result:

ok

Test #102:

score: 80

Accepted

time: 0ms

memory: 4724kb

input:

output:

result:

ok

Test #103:

score: 80

Accepted

time: 0ms

memory: 4680kb

input:

output:

result:

ok

Test #104:

score: 80

Accepted

time: 0ms

memory: 4788kb

input:

output:

result:

ok

Test #105:

score: 80

Accepted

time: 0ms

memory: 4756kb

input:

output:

result:

ok

Test #106:

score: 80

Accepted

time: 0ms

memory: 4744kb

input:

output:

result:

ok

Test #107:

score: 80

Accepted

time: 0ms

memory: 4736kb

input:

output:

result:

ok

Extra Test:

score: 0

Extra Test Passed