Submission #1072982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072982		edogawa_something	Brought Down the Grading Server? (CEOI23_balance)	C++17	30 / 100	450 ms	409288 KiB

balance

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
const ll M=1e6;
ll n,s,t,cnt[M],curc[M],rc[M];
vii a[M],ans[M];
vii res;
bool vis[M];
vector<pii>edges;
vector<pii>eul[M],adj[M];
map<pii,ll>col;
vii euler;
ll cc[M],ccc[M];
void dfs(ll x,ll pa=-1) {
    if(vis[x])
        return;
    vis[x]=1;
    if(eul[x][0].F==x) {
        ans[eul[x][0].S].pb(x),ans[eul[x][0].S].pb(x);
        return;
    }
    if(eul[x][0].F==pa)
        swap(eul[x][0],eul[x][1]);
    ans[eul[x][0].S].pb(x),ans[eul[x][0].S].pb(eul[x][0].F);
    dfs(eul[x][0].F,x);
}
vector<pii>ee;
void tour(ll x,ll par=-1) {
    while(adj[x].size()>0) {
        if(vis[adj[x].back().S]) {
            adj[x].pop_back();
            continue;
        }
        ll y=adj[x].back().F;
        vis[adj[x].back().S]=1;
        adj[x].pop_back();
        tour(y,x);
    }
  //  cout<<x<<' '<<par<<endl;
    if(par>=0)
        ee.pb({x,par});
}
void DaC(ll sz,vector<pii> e) {
    //cout<<e.size()<<' ';
    for(int i=0;i<2*n;i++)
        adj[i].clear();
    if(sz==2) {
        for(int i=0;i<n;i++)
            cc[i]=ans[i].size();
        for(int i=0;i<n;i++)
            vis[i]=0;
        for(auto it:e)
            adj[it.F].pb({it.S,0}),adj[it.S].pb({it.F,0});
        vector<pair<ll,pii>>v;
        for(int i=0;i<n;i++) {
            v.pb({i,{adj[i][0].F-n,adj[i][1].F-n}});
        }
        for(int i=0;i<n;i++)
            eul[i].clear();
        for(auto it:v) {
            eul[it.S.F].pb({it.S.S,it.F});
            eul[it.S.S].pb({it.S.F,it.F});
        }
        for(int i=0;i<n;i++) {
            assert(eul[i].size()==2);
        }
        for(int i=0;i<n;i++) {
            if(!vis[i])
                dfs(i);
        }
        for(int i=0;i<n;i++)
            vis[i]=0;
        return;
    }
    ll c=0;
    for(auto it:e) {
        vis[c]=0;
        adj[it.F].pb({it.S,c});
        adj[it.S].pb({it.F,c++});
       // cout<<it.F<<' '<<it.S<<' '<<c<<endl;
    }
    ee.clear();
    tour(0);
    vector<pii>e1,e2;
    for(int i=0;i<ee.size();i++) {
        if(i%2==0)
            e1.pb(ee[i]);
        else
            e2.pb(ee[i]);
    }
    euler.clear();
    DaC(sz/2,e1),DaC(sz/2,e2);
}
int main() {
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>n>>s>>t;
    t=0;
    for(int i=0;i<n;i++) {
        a[i].resize(s);
        for(int j=0;j<s;j++) {
            cin>>a[i][j];
            cnt[a[i][j]]++;
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<s;j++) {
            if(cnt[a[i][j]]%s==0)
                curc[a[i][j]]=t++;
            cnt[a[i][j]]--;
            rc[curc[a[i][j]]]=a[i][j];
            edges.pb({curc[a[i][j]]+n,i});
        }
    }
    DaC(s,edges);
    for(int i=0;i<n;i++) {
        for(auto it:ans[i])
            cout<<rc[it]<<' ';
        cout<<'\n';
    }
    return 0;
}

Compilation message (stderr)

balance.cpp: In function 'void DaC(ll, std::vector<std::pair<long long int, long long int> >)':
balance.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<ee.size();i++) {
      |                 ~^~~~~~~~~~

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