Submission #1370039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370039		dragonlyz123	A String Problem (EGOI25_stringproblem)	C++20	100 / 100	79 ms	26448 KiB

Main

/*
─────────────────────────────────────────────────────────────────────────────────────
 ██╗     ███████╗███████╗    ██╗   ██╗███████╗███╗   ██╗    ███████╗███████╗███████╗
 ██║     ██╔════╝██╔════╝    ╚██╗ ██╔╝██╔══██╗████╗  ██║    ╚══███╔╝██╔════╝██╔════╝
 ██║     █████╗  █████╗       ╚████╔╝ ███████║██╔██╗ ██║      ███╔╝ █████╗  █████╗
 ██║     ██╔══╝  ██╔══╝        ╚██╔╝  ██╔══██║██║╚██╗██║     ███╔╝  ██╔══╝  ██╔══╝
 ███████╗███████╗███████╗       ██║   ██║  ██║██║ ╚████║    ███████╗███████╗███████╗
 ╚══════╝╚══════╝╚══════╝       ╚═╝   ╚═╝  ╚═╝╚═╝  ╚═══╝    ╚══════╝╚══════╝╚══════╝
 ─────────────────────────────────────────────────────────────────────────────────────
							» Stay hungry, stay foolish. «
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
ll ll_max = 2e18;
ll ll_min = -2e18;
 
void set_io(string name = "") {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

void solve() {
	ll n; cin >> n;
	vector<vector<ll>> ab(n, vector<ll>(2));
	ll d = -1, e = -1;
	unordered_map<ll, ll> c;
	ll j = n - 1;
	vector<vector<ll>> z(2 * n, vector<ll>(2));
	for (ll i = 0; i < n; i++) {
		cin >> ab[i][0] >> ab[i][1];
		z[ab[i][0]][0] = ab[i][1];
		z[ab[i][1]][0] = ab[i][0];
		z[ab[i][0]][1] = i;
		z[ab[i][1]][1] = i;
		if ((ab[i][1] - ab[i][0]) % 2 != 0) {
			ll y = (ab[i][0] + ab[i][1] - j + 2 * n) % (2 * n);
			c[y]++;
			if (c[y] > e) {
				d = y;
				e = c[y];
			}
		}
	}
	if (d == -1 && e == -1) {
		d = n;
		e = 0;
	}
	vector<bool> done(2 * n, false);
	vector<vector<ll>> ans;
	for (ll i = 0; i < 2 * n; i++) {
		queue<ll> q;
		q.emplace(i);
		while (!q.empty()) {
			ll y = q.front();
			q.pop();
			ll k = (d - y + j + 2 * n) % (2 * n);
			if (k != z[y][0]) {
				if (done[y] && !done[z[y][0]]) {
					q.emplace(z[y][0]);
				} else if (!done[y]) {
					vector<ll> m = {z[y][1], z[y][0], k};
					ans.emplace_back(m);
					q.emplace(z[k][0]);
					done[y] = true;
					done[k] = true;
				}
			} else {
				done[y] = true;
				done[k] = true;
			}
		}
	}
	cout << ans.size() << "\n";
	for (vector<ll> l : ans) {
		cout << l[0] << " " << l[1] << " " << l[2] << "\n";
	}
}

int main() {
    set_io();
    // ll t; cin >> t;
    // while (t--) {
    //     solve();
    // }
    solve();
    return 0;
}

// g++-15 -std=c++23 -O2 solution.cpp -o solution
// ./solution

Compilation message (stderr)

Main.cpp: In function 'void set_io(std::string)':
Main.cpp:26:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 freopen((name + ".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |                 freopen((name + ".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 12 / 12
• Subtask 4: 28 / 28
• Subtask 5: 30 / 30