Submission #1344581

#TimeUsernameProblemLanguageResultExecution timeMemory
1344581kokorooA String Problem (EGOI25_stringproblem)C++20
100 / 100
327 ms43920 KiB
#include<bits/stdc++.h>
//#include<atcoder/all>

using namespace std;
//using namespace atcoder;
#define rep(i,n) for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define print(a) cout<<a<<endl
typedef long long ll;
#define yn(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define YN(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define so(a) sort(a.begin(),a.end())
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vs vector<string>
#define pb push_back
#define a2i(a,s) (ll)(a-s)
#define i2a(s,a) (char)(s+a)
#define ssize(a) a.size()
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<pair<ll,ll>,pair<ll,ll>> P4;

typedef pair<ll, ll> Pll;
typedef pair<ll,Pll> Plll;
typedef pair<Pii, int> Piii;
const ll INF = 1000000000000000000;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;

}
using ull=unsigned long long;

int main(){
//入力

	cin.tie(0);
	ios::sync_with_stdio(0);


	ll n;
	cin>>n;

	vector<Pll> g(n);
	map<Pll,ll> mp;
	map<ll,ll> mp2;

	for(ll i=0;i<n;i++){
		ll a,b;
		cin>>a>>b;
		if(a>b)swap(a,b);
		g[i]={a,b};

		ll p=(b-a)/2;
		if((b-a)%2==1){
			ll P=(a+2*n-b)/2;
			mp[{(a+p)%(2*n),(a+p+1)%(2*n)}]++;
			mp[{(b+P)%(2*n),(b+P+1)%(2*n)}]++;

		}
		mp2[a]=i;
		mp2[b]=i;

	}


	ll ans=-INF;
	Pll p={0,0};
	for(ll i=0;i<2*n-1;i++){
		if(ans<mp[{i,i+1}]){
			ans=mp[{i,i+1}];
			p={i,i+1};
		}
	}
	if(ans<mp[{2*n-1,0}]){
		ans=mp[{2*n-1,0}];
		p={2*n-1,0};

	}

	cout<<n-ans<<endl;

//判定

	vector<ll> v(n);
	vector<ll> V(2*n);

	map<ll,ll> mp3;
	for(ll i=0;i<n;i++){
		mp3[p.first]=p.second;
		mp3[p.second]=p.first;
		p.second++;
		p.first--;

		p.second=p.second%(2*n);
		p.first=(p.first+2*n)%(2*n);

	}

	for(ll i=0;i<n;i++){
		if(v[i]==0){
			v[i]=1;
			ll X=mp3[g[i].first];
			if(X==g[i].second){
				V[g[i].first]=1;
				V[g[i].second]=1;
				continue;
			}

			V[g[i].first]=1;

			cout<<i<<" "<<g[i].second<<" "<<X<<endl;
			V[X]=1;
			X=g[i].second;

			while(true){
				ll nx=mp3[X];
				ll ny=mp2[nx];
				v[ny]=1;
				V[nx]=1;
				V[X]=1;

				if(g[ny].first==nx){
					cout<<ny<<" "<<g[ny].second<<" "<<X<<endl;
					X=g[ny].second;
				}
				else {
					cout<<ny<<" "<<g[ny].first<<" "<<X<<endl;
					X=g[ny].first;
				}
				if(V[X]==1)break;
			}

		}
	}


	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...