QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#330073 | #6537. One, Two, Three | 5ab | RE | 0ms | 0kb | C++20 | 2.6kb | 2024-02-17 11:59:55 | 2024-02-17 11:59:56 |
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