Submission #1282463

#TimeUsernameProblemLanguageResultExecution timeMemory
1282463user736482Brought Down the Grading Server? (CEOI23_balance)C++20
100 / 100
436 ms90860 KiB
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
ll fct[1000007];
ll fp(ll a,ll b){
    ll c=1;while(b){if(b&1)c=(c*a)%MOD;a=(a*a)%MOD;b/=2;}
    return c;
}
vii g[100007];
ll sz[100007];
bool vis[1000007];
vector<vi>v;
ll s;
void psc(ll x){
    //cout<<x<<" ";
    while(g[x].size() && vis[g[x].back().ss])g[x].pop_back();
    if(g[x].empty())return;
    vis[g[x].back().ss]=1;
    if(g[x].back().ff<0){
        //cout<<x<<" "<<abs(g[x].back().ff)<<"\n";
        ll y=g[x].back().ss;
        swap(v[y/(s/2)][y%(s/2)],v[y/(s/2)][s-1-y%(s/2)]);
    }
    sz[x]--;
    sz[abs(g[x].back().ff)]--;
    psc(abs(g[x].back().ff));
}

vector<vi> dz(ll k,vector<vi>V){
    //cout<<V<<"\n";
    v=V;
    if(v[0].size()==1)return v;
    s=v[0].size();
    vi v2;
    for(ll i=0;i<k;i++){
        for(ll j=0;j<s;j++){
            g[v[i][j]].clear();
            sz[v[i][j]]=0;
        }
    }
     for(ll i=0;i<k;i++){
        for(ll j=0;j<s;j++){
            sz[v[i][j]]++;
        }
    }
    for(ll i=0;i<k;i++){
        for(ll j=0;j<s/2;j++){
            g[v[i][j]].pb({v[i][s-1-j],i*(s/2)+j});
            g[v[i][s-1-j]].pb({-v[i][j],i*(s/2)+j});
            vis[i*(s/2)+j]=0;
            v2.pb(v[i][j]);v2.pb(v[i][s-1-j]);
        }
    }
    //cout<<v2<<" ";
    for(ll i : v2){
        if(sz[i]&1)psc(i);
    }
    for(ll i : v2)if(sz[i])psc(i);
    vector<vi>v1,v5;
    for(ll i=0;i<k;i++){
        v1.pb({});
        v5.pb({});
        for(ll j=0;j<s;j++)if(j<s/2)v1.back().pb(v[i][j]);else v5.back().pb(v[i][j]);
    }
    v1=dz(k,v1);
    v5=dz(k,v5);
    for(ll i=0;i<k;i++)for(ll j : v5[i])v1[i].pb(j);
    return v1;
}
void solve(){
    ll n,s,t,a;
    vector<vi>v;
    cin>>n>>s>>t;
    for(ll i=0;i<n;i++){
        v.pb({});
        for(ll j=0;j<s;j++){
            cin>>a;
            v.back().pb(a);
        }
    }
    v=dz(n,v);
    for(auto i : v){
        for(ll j : i)cout<<j<<" ";cout<<"\n";
    }
}
int main(){
    fct[0]=1;
    for(ll i=1;i<1000007;i++)fct[i]=(fct[i-1]*i)%MOD;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        solve();
    }
}
#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...
#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...