QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330073#6537. One, Two, Three5abRE 0ms0kbC++202.6kb2024-02-17 11:59:552024-02-17 11:59:56

Judging History

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

  • [2024-02-17 11:59:56]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-02-17 11:59:55]
  • 提交

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);
		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 });
	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()
{
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	
	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

详细

Test #1:

score: 0
Dangerous Syscalls

input:

6
3 1 2 2 3 1

output:


result: