QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330077#6537. One, Two, Three5abWA 1846ms7836kbC++202.6kb2024-02-17 12:02:182024-02-17 12:02:18

Judging History

你现在查看的是最新测评结果

  • [2024-02-17 12:02:18]
  • 评测
  • 测评结果:WA
  • 用时:1846ms
  • 内存:7836kb
  • [2024-02-17 12:02:18]
  • 提交

answer

/* name: count
 * author: 5ab
 * created at: 2024-02-17
 */
#include <iostream>
#include <random>
#include <chrono>
#include <vector>
#include <tuple>
#include <set>
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 = 6e5, OPT = 10000;

int a[N], ord[N], n;

vector<tuple<int, int, int>> ans, cur;
set<int> pos[4];
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

void solve()
{
	cur.clear();
	for (int i = 0; i < 4; i++)
		pos[i].clear();
	for (int i = 0; i < n; i++)
	{
		ord[i] = i;
		pos[a[i]].insert(pos[a[i]].end(), i);
	}
	shuffle(ord, ord + n, rng);
	
	auto pre = [&](set<int>& s, int x)
	{
		auto it = s.lower_bound(x);
		return it == s.begin() ? -1 : *prev(it);
	};
	auto nxt = [&](set<int>& s, int x)
	{
		auto it = s.lower_bound(x);
		return it == s.end() ? -1 : *it;
	};
	
	auto tryGet = [&](int p, int t) -> pair<int, int>
	{
		int ap = 1, bp = 3;
		if (t == 1)
			swap(ap, bp);
		int pr = pre(pos[ap], p), nx = nxt(pos[bp], p);
		// cerr << pr << " " << nx << endl;
		if (pr == -1 || nx == -1)
			return { -1, -1 };
		pos[ap].erase(pr), pos[bp].erase(nx), pos[2].erase(p);
		return { pr, nx };
	};
	auto doIns = [&](int i)
	{
		int x = rng() % 2;
		auto [pr, nx] = tryGet(i, x);
		if (pr != -1)
			cur.emplace_back(pr, i, nx);
		else
		{
			tie(pr, nx) = tryGet(i, x ^ 1);
			if (pr != -1)
				cur.emplace_back(pr, i, nx);
		}
	};
	
	for (int _i = 0; _i < n; _i++)
	{
		int i = ord[_i];
		if (a[i] == 2)
			doIns(i);
	}
	if (ssz(cur) > ssz(ans))
		ans = cur;
	// discrete_distribution Ty({ 10, 10, 10, 1 });
	if (ssz(cur) == 0)
		return;
	int opc = OPT;
	vector<int> ips;
	while (opc--)
	{
		int x = rng() % ssz(cur);
		swap(cur[x], cur.back());
		pos[a[get<0>(cur.back())]].insert(get<0>(cur.back()));
		pos[2].insert(get<1>(cur.back()));
		pos[a[get<2>(cur.back())]].insert(get<2>(cur.back()));
		cur.pop_back();
		
		ips.assign(all(pos[2]));
		shuffle(all(ips), rng);
		
		for (auto p : ips)
			doIns(p);
		if (ssz(cur) > ssz(ans))
			ans = cur;
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	while (double(clock()) / CLOCKS_PER_SEC < 1.5)
		solve();
	cout << ssz(ans) << "\n";
	for (auto [x, y, z] : ans)
		cout << x << " " << y << " " << z << "\n";
	
	// cerr << clock() << endl;
	
	return 0;
}
// started coding at: 02-17 11:26:31

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1503ms
memory: 5884kb

input:

6
3 1 2 2 3 1

output:

2
1 3 4
0 2 5

result:

ok count=2

Test #2:

score: 0
Accepted
time: 1094ms
memory: 5728kb

input:

6
2 1 3 1 3 2

output:

0

result:

ok count=0

Test #3:

score: 0
Accepted
time: 1505ms
memory: 5900kb

input:

3000
1 1 1 1 1 3 1 1 3 3 1 3 1 1 2 3 1 1 2 1 2 1 3 3 3 1 1 2 1 2 2 3 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 3 3 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 2 3 1 1 1 1 3 3 2 1 3 1 1 2 3 1 2 3 1 1 1 2 1 1 1 1 2 3 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 3 1 3 3 1 1 1 1 3 1 1 2 1 1 1 3 3 1 1 1 1 2 1 1 1 1 1 2 3 3 1...

output:

499
2577 2583 2584
1841 1843 1849
773 774 790
2731 2737 2739
213 214 217
2212 2213 2216
467 473 476
2609 2617 2618
594 596 598
1589 1594 1596
2909 2912 2914
333 334 335
1277 1278 1281
180 181 182
2388 2389 2390
627 628 629
2968 2969 2970
2262 2264 2266
1587 1600 1601
2549 2550 2553
2441 2442 2443
17...

result:

ok count=499

Test #4:

score: 0
Accepted
time: 1498ms
memory: 6040kb

input:

3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
1373 1374 2901

result:

ok count=1

Test #5:

score: 0
Accepted
time: 1846ms
memory: 7836kb

input:

3000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

1
1755 2677 2819

result:

ok count=1

Test #6:

score: -100
Wrong Answer
time: 1506ms
memory: 6004kb

input:

1500
1 1 1 2 1 1 1 2 2 2 2 2 1 1 3 1 2 2 3 1 2 2 2 2 1 2 1 2 1 1 3 1 2 2 2 2 1 1 3 1 1 2 2 3 2 1 3 1 1 2 2 2 1 2 2 2 2 2 1 2 3 2 3 2 3 2 1 3 2 1 2 3 2 2 3 2 3 1 1 3 1 3 1 3 3 3 1 3 3 3 1 1 3 1 3 1 3 1 1 1 3 1 3 1 3 3 1 1 1 3 1 1 3 1 1 1 1 1 3 3 3 3 1 3 1 1 1 1 3 3 3 3 3 3 1 3 1 1 1 3 1 3 1 1 1 1 3 1...

output:

461
543 693 786
2 3 79
193 1372 1408
798 1277 1450
538 1137 1456
248 944 1187
439 1285 1386
518 1241 1467
230 1328 1383
379 1388 1441
462 1045 1063
394 1213 1361
342 938 1012
14 22 78
441 708 838
357 1248 1458
526 639 794
336 690 1085
821 1310 1425
440 884 910
266 1154 1198
389 929 1003
472 945 1007...

result:

wrong answer the number of matches is different