QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#330077 | #6537. One, Two, Three | 5ab | WA | 1846ms | 7836kb | C++20 | 2.6kb | 2024-02-17 12:02:18 | 2024-02-17 12:02:18 |
Judging History
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
详细
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