Submission #1234163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234163		Malix	Brought Down the Grading Server? (CEOI23_balance)	C++20	50 / 100	2098 ms	116252 KiB

balance

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,s,t;
vii X;

void solve(int l,int r,vector<multiset<int>> A){
    if(l==r){
        REP(i,1,t+1)for(auto u:A[i])X[u][l]=i;
        return;
    }
    int m=(l+r)/2;
    vector<multiset<int>> Y(t+1),Z(t+1);
    vector<multiset<int>> B(n);
    REP(i,1,t+1)for(auto u:A[i])B[u].insert(i);
    REP(i,1,t+1){
        if(A[i].empty())continue;
        int p=1;
        while(!A[i].empty()){
            p=1-p;
            set<int> st;
            vi arr;
            int x=i;
            bool f=1;
            while(f){
                while(!A[x].empty()&&B[*A[x].begin()].empty())A[x].erase(A[x].begin());
                if(A[x].empty())break;
                int z=*A[x].begin();
                A[x].erase(A[x].begin());
                B[z].erase(B[z].find(x));
                int y=*B[z].begin();
                A[y].erase(A[y].find(z));
                B[z].erase(B[z].begin());
                st.insert(x);arr.PB(x);
                if(p%2==0){
                    Y[x].insert(z);
                    Z[y].insert(z);
                }
                else{
                    Y[y].insert(z);
                    Z[x].insert(z);
                }
                if(st.count(y)){
                    while(arr.back()!=y){
                        st.erase(arr.back());
                        arr.pop_back();
                    }
                    st.erase(arr.back());
                    arr.pop_back();
                    if(arr.empty())break;
                }
                x=y;
            }
        }
    }
    solve(l,m,Y);
    solve(m+1,r,Z);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>s>>t;
    X.resize(n,vi(s));
    vector<multiset<int>> A(t+1);
    REP(i,0,n)REP(j,0,s){
        int x;cin>>x;
        A[x].insert(i);
    }
    solve(0,s-1,A);
    REP(i,0,n){
        REP(j,0,s)cout<<X[i][j]<<" ";
        cout<<"\n";
    }
}

• 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: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 0 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10