제출 #1366862

#제출 시각아이디문제언어결과실행 시간메모리
1366862weedywelonA String Problem (EGOI25_stringproblem)C++20
100 / 100
29 ms9708 KiB
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>
#include <map>
#include <chrono>
#include <random>
#include <bitset>
#include <tuple>
#define SZ(x) int(x.size())
#define FR(i,a,b) for(int i=(a);i<(b);++i)
#define FOR(i,n) FR(i,0,n)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define A first
#define B second
#define mp(a,b) make_pair(a,b)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef unsigned __int128 U128;
typedef __int128 I128;
typedef std::pair<int,int> PII;
typedef std::pair<LL,LL> PLL;
using namespace std;

const LL MAXN=2e5+5;
LL p[MAXN][2], v[MAXN], at[MAXN];
bool good[MAXN];

signed main(){
	FAST;
	LL n; cin>>n;
	FOR(i,n){
		LL a,b; cin>>a>>b;
		p[i][0]=a;
		p[i][1]=b;
		at[a]=at[b]=i;
		v[(a+b)%(2*n)]++;
	}
	
	LL mx=0, id=0;
	for (int i=1; i<2*n; i+=2){
		if (v[i]>=mx){
			mx=v[i];
			id=i;
		}
	}
	cout<<n-mx<<"\n";
	
	vector<pair<LL,PLL> > q;
	FOR(i,n){
		LL a=p[i][0], b=p[i][1];
		if ((a+b)%(2*n)!=id) q.push_back(mp(i, mp(a,b)));
		else good[a]=good[b]=true;	
	}
	
	FOR(j,SZ(q)){
		LL i=q[j].A, a=q[j].B.A, b=q[j].B.B;
		if (good[a] || good[b]) continue;
		
		LL c=(2*n+id-a)%(2*n);
		while (at[c]!=-1){
			cout<<i<<" "<<b<<" "<<c<<"\n";
			at[b]=-1;
			good[a]=good[c]=true;
			
			LL nxt=at[c], na=p[nxt][0], nc=p[nxt][1];
			if (na==c) swap(na,nc);
			b=c;
			a=na;
			c=(2*n+id-a)%(2*n);
			i=nxt;
		}
		cout<<i<<" "<<b<<" "<<c<<"\n";
		good[a]=good[c]=true;
	}
	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…