Submission #1165458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165458		Mighilon	Brought Down the Grading Server? (CEOI23_balance)	C++20	100 / 100	744 ms	178160 KiB

balance

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n,s,t;
void f(vector<vi>& c){
	int m=sz(c[0]);
	if(m<=1)
		return;
	vector<vi> a(sz(c)),b(sz(c)); 
	F0R(i,sz(c)){
		F0R(j,sz(c[0])/2){
			a[i].pb(c[i][j]);
			b[i].pb(c[i][j+sz(c[0])/2]);
		}
	}
	vector<vi> x=a;
	trav(i,b)x.pb(i);
	f(x);
	F0R(i,sz(x)/2){
		a[i]=x[i];
		b[i]=x[i+sz(x)/2];
	}
	vi e;
	vb vis;
	vector<vi> adj(t+1);
	F0R(i,sz(a[0])){
		fill(all(vis),0);
		e.resize(sz(a));
		vis.resize(sz(a));
		set<int> st;
		F0R(j,sz(a)){
			e[j]=a[j][i]^b[j][i];
			adj[a[j][i]].pb(j);
			adj[b[j][i]].pb(j);
			st.insert(a[j][i]);
			st.insert(b[j][i]);
		}
		trav(j,st){
			if(sz(adj[j])%2==1){
				e.pb(j);
				vis.pb(0);
				adj[j].pb(sz(e)-1);
				adj[0].pb(sz(e)-1);
			}
		}
		vi z(sz(e));
		vi path;
		function<void(int)> euler=[&](int v)->void{
			while(!adj[v].empty()){
				int id=adj[v].back();
				adj[v].pop_back();
				int u=e[id]^v;
				if(vis[id])continue;
				vis[id]=true;
				euler(u);
				if(id<sz(a)) z[id]=v;
			}
			path.push_back(v);
		};
		trav(j,st){
			euler(j);
		}
		F0R(j,sz(a)){
			if(a[j][i]!=z[j])
				swap(a[j][i],b[j][i]);
		}
	}
	F0R(i,sz(c)){
		c[i]=a[i];
		trav(j,b[i])
			c[i].pb(j);
	}
}
 
void solve(){
	cin>>n>>s>>t;
	vector<vi> a(n,vi(s));
	F0R(i,n){
		F0R(j,s){
			cin>>a[i][j];
		}
	}
	f(a);
	F0R(i,n){
		F0R(j,s){
			cout<<a[i][j]<<" ";
		}
		cout<<nl;
	}
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 5 / 5
• Subtask 2-3: 5 / 5
• Subtask 3-1: 15 / 15
• Subtask 3-2: 5 / 5
• Subtask 3-3: 5 / 5
• Subtask 4-1: 20 / 20
• Subtask 4-2: 10 / 10
• Subtask 4-3: 10 / 10