oj.uz

Submission #1072994

# Submission time Handle Problem Language Result Execution time Memory
1072994 2024-08-24T08:07:02 Z edogawa_something Brought Down the Grading Server? (CEOI23_balance) C++17
15 / 100
 183 ms 253536 KB 
#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++) {
            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();
    for(int i=0;i<n;i++) {
        if(adj[i].empty()||vis[adj[i][0].S])
        tour(i);
    }
    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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 191020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 190980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 131136 KB Correct
2 Correct 127 ms 129232 KB Correct
3 Correct 118 ms 123832 KB Correct
4 Correct 99 ms 124596 KB Correct
5 Correct 138 ms 131252 KB Correct
6 Correct 132 ms 130744 KB Correct
7 Correct 150 ms 126904 KB Correct
8 Correct 109 ms 131896 KB Correct
9 Correct 107 ms 132536 KB Correct
10 Correct 108 ms 131168 KB Correct
11 Correct 100 ms 131008 KB Correct

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 131136 KB Correct
2 Correct 127 ms 129232 KB Correct
3 Correct 118 ms 123832 KB Correct
4 Correct 99 ms 124596 KB Correct
5 Correct 138 ms 131252 KB Correct
6 Correct 132 ms 130744 KB Correct
7 Correct 150 ms 126904 KB Correct
8 Correct 109 ms 131896 KB Correct
9 Correct 107 ms 132536 KB Correct
10 Correct 108 ms 131168 KB Correct
11 Correct 100 ms 131008 KB Correct
12 Correct 127 ms 131000 KB Correct
13 Correct 129 ms 129248 KB Correct
14 Correct 121 ms 123828 KB Correct
15 Correct 90 ms 124596 KB Correct
16 Correct 124 ms 131252 KB Correct
17 Correct 130 ms 130744 KB Correct
18 Correct 124 ms 126904 KB Correct
19 Correct 107 ms 132020 KB Correct
20 Correct 108 ms 132564 KB Correct
21 Correct 95 ms 131144 KB Correct
22 Correct 98 ms 131008 KB Correct
23 Runtime error 183 ms 253536 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 190980 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3-1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 94232 KB Output for core 1 doesn't match the input tasks
2 Halted 0 ms 0 KB -

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 94232 KB Output for core 1 doesn't match the input tasks
2 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 94232 KB Output for core 1 doesn't match the input tasks
2 Halted 0 ms 0 KB -

Subtask #4-1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 131136 KB Correct
2 Correct 127 ms 129232 KB Correct
3 Correct 118 ms 123832 KB Correct
4 Correct 99 ms 124596 KB Correct
5 Correct 138 ms 131252 KB Correct
6 Correct 132 ms 130744 KB Correct
7 Correct 150 ms 126904 KB Correct
8 Correct 109 ms 131896 KB Correct
9 Correct 107 ms 132536 KB Correct
10 Correct 108 ms 131168 KB Correct
11 Correct 100 ms 131008 KB Correct
12 Incorrect 48 ms 94232 KB Output for core 1 doesn't match the input tasks
13 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 131136 KB Correct
2 Correct 127 ms 129232 KB Correct
3 Correct 118 ms 123832 KB Correct
4 Correct 99 ms 124596 KB Correct
5 Correct 138 ms 131252 KB Correct
6 Correct 132 ms 130744 KB Correct
7 Correct 150 ms 126904 KB Correct
8 Correct 109 ms 131896 KB Correct
9 Correct 107 ms 132536 KB Correct
10 Correct 108 ms 131168 KB Correct
11 Correct 100 ms 131008 KB Correct
12 Correct 127 ms 131000 KB Correct
13 Correct 129 ms 129248 KB Correct
14 Correct 121 ms 123828 KB Correct
15 Correct 90 ms 124596 KB Correct
16 Correct 124 ms 131252 KB Correct
17 Correct 130 ms 130744 KB Correct
18 Correct 124 ms 126904 KB Correct
19 Correct 107 ms 132020 KB Correct
20 Correct 108 ms 132564 KB Correct
21 Correct 95 ms 131144 KB Correct
22 Correct 98 ms 131008 KB Correct
23 Runtime error 183 ms 253536 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #4-3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 191020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -