oj.uz

Submission #1072980

# Submission time Handle Problem Language Result Execution time Memory
1072980 2024-08-24T07:59:25 Z edogawa_something Brought Down the Grading Server? (CEOI23_balance) C++17
30 / 100
 341 ms 302368 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=4e5;
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

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 44 ms 76696 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 76728 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 75820 KB Correct
2 Correct 114 ms 73868 KB Correct
3 Correct 106 ms 68432 KB Correct
4 Correct 79 ms 68744 KB Correct
5 Correct 119 ms 76044 KB Correct
6 Correct 123 ms 75480 KB Correct
7 Correct 134 ms 71596 KB Correct
8 Correct 97 ms 76780 KB Correct
9 Correct 96 ms 77240 KB Correct
10 Correct 76 ms 75876 KB Correct
11 Correct 91 ms 75704 KB Correct

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 75820 KB Correct
2 Correct 114 ms 73868 KB Correct
3 Correct 106 ms 68432 KB Correct
4 Correct 79 ms 68744 KB Correct
5 Correct 119 ms 76044 KB Correct
6 Correct 123 ms 75480 KB Correct
7 Correct 134 ms 71596 KB Correct
8 Correct 97 ms 76780 KB Correct
9 Correct 96 ms 77240 KB Correct
10 Correct 76 ms 75876 KB Correct
11 Correct 91 ms 75704 KB Correct
12 Correct 117 ms 75732 KB Correct
13 Correct 105 ms 73916 KB Correct
14 Correct 108 ms 68280 KB Correct
15 Correct 70 ms 68660 KB Correct
16 Correct 98 ms 76048 KB Correct
17 Correct 135 ms 75700 KB Correct
18 Correct 117 ms 71608 KB Correct
19 Correct 107 ms 76700 KB Correct
20 Correct 83 ms 77240 KB Correct
21 Correct 98 ms 75968 KB Correct
22 Correct 72 ms 75756 KB Correct
23 Runtime error 110 ms 136888 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #2-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 76728 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3-1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37980 KB Correct
2 Correct 21 ms 40540 KB Correct
3 Correct 22 ms 40408 KB Correct
4 Correct 22 ms 40540 KB Correct
5 Correct 17 ms 39584 KB Correct
6 Correct 27 ms 39828 KB Correct
7 Correct 19 ms 40288 KB Correct
8 Correct 24 ms 40536 KB Correct
9 Correct 20 ms 40280 KB Correct
10 Correct 19 ms 40340 KB Correct
11 Correct 17 ms 40292 KB Correct
12 Correct 18 ms 40008 KB Correct
13 Correct 18 ms 39840 KB Correct
14 Correct 17 ms 39840 KB Correct

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37980 KB Correct
2 Correct 21 ms 40540 KB Correct
3 Correct 22 ms 40408 KB Correct
4 Correct 22 ms 40540 KB Correct
5 Correct 17 ms 39584 KB Correct
6 Correct 27 ms 39828 KB Correct
7 Correct 19 ms 40288 KB Correct
8 Correct 24 ms 40536 KB Correct
9 Correct 20 ms 40280 KB Correct
10 Correct 19 ms 40340 KB Correct
11 Correct 17 ms 40292 KB Correct
12 Correct 18 ms 40008 KB Correct
13 Correct 18 ms 39840 KB Correct
14 Correct 17 ms 39840 KB Correct
15 Correct 14 ms 37980 KB Correct
16 Correct 22 ms 40540 KB Correct
17 Correct 19 ms 40408 KB Correct
18 Correct 22 ms 40540 KB Correct
19 Correct 17 ms 39584 KB Correct
20 Correct 23 ms 39808 KB Correct
21 Correct 19 ms 40364 KB Correct
22 Correct 19 ms 40536 KB Correct
23 Correct 19 ms 40280 KB Correct
24 Correct 19 ms 40540 KB Correct
25 Correct 19 ms 40292 KB Correct
26 Correct 19 ms 39844 KB Correct
27 Correct 21 ms 39836 KB Correct
28 Correct 20 ms 39840 KB Correct
29 Runtime error 46 ms 81464 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #3-3
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37980 KB Correct
2 Correct 21 ms 40540 KB Correct
3 Correct 22 ms 40408 KB Correct
4 Correct 22 ms 40540 KB Correct
5 Correct 17 ms 39584 KB Correct
6 Correct 27 ms 39828 KB Correct
7 Correct 19 ms 40288 KB Correct
8 Correct 24 ms 40536 KB Correct
9 Correct 20 ms 40280 KB Correct
10 Correct 19 ms 40340 KB Correct
11 Correct 17 ms 40292 KB Correct
12 Correct 18 ms 40008 KB Correct
13 Correct 18 ms 39840 KB Correct
14 Correct 17 ms 39840 KB Correct
15 Correct 14 ms 37980 KB Correct
16 Correct 22 ms 40540 KB Correct
17 Correct 19 ms 40408 KB Correct
18 Correct 22 ms 40540 KB Correct
19 Correct 17 ms 39584 KB Correct
20 Correct 23 ms 39808 KB Correct
21 Correct 19 ms 40364 KB Correct
22 Correct 19 ms 40536 KB Correct
23 Correct 19 ms 40280 KB Correct
24 Correct 19 ms 40540 KB Correct
25 Correct 19 ms 40292 KB Correct
26 Correct 19 ms 39844 KB Correct
27 Correct 21 ms 39836 KB Correct
28 Correct 20 ms 39840 KB Correct
29 Runtime error 46 ms 81464 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -

Subtask #4-1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 75820 KB Correct
2 Correct 114 ms 73868 KB Correct
3 Correct 106 ms 68432 KB Correct
4 Correct 79 ms 68744 KB Correct
5 Correct 119 ms 76044 KB Correct
6 Correct 123 ms 75480 KB Correct
7 Correct 134 ms 71596 KB Correct
8 Correct 97 ms 76780 KB Correct
9 Correct 96 ms 77240 KB Correct
10 Correct 76 ms 75876 KB Correct
11 Correct 91 ms 75704 KB Correct
12 Correct 14 ms 37980 KB Correct
13 Correct 21 ms 40540 KB Correct
14 Correct 22 ms 40408 KB Correct
15 Correct 22 ms 40540 KB Correct
16 Correct 17 ms 39584 KB Correct
17 Correct 27 ms 39828 KB Correct
18 Correct 19 ms 40288 KB Correct
19 Correct 24 ms 40536 KB Correct
20 Correct 20 ms 40280 KB Correct
21 Correct 19 ms 40340 KB Correct
22 Correct 17 ms 40292 KB Correct
23 Correct 18 ms 40008 KB Correct
24 Correct 18 ms 39840 KB Correct
25 Correct 17 ms 39840 KB Correct
26 Correct 112 ms 75880 KB Correct
27 Correct 118 ms 73812 KB Correct
28 Correct 93 ms 68300 KB Correct
29 Correct 72 ms 68796 KB Correct
30 Correct 102 ms 75996 KB Correct
31 Correct 120 ms 75704 KB Correct
32 Correct 113 ms 71604 KB Correct
33 Correct 89 ms 76728 KB Correct
34 Correct 87 ms 77240 KB Correct
35 Correct 108 ms 76048 KB Correct
36 Correct 78 ms 75844 KB Correct
37 Correct 24 ms 37980 KB Correct
38 Correct 22 ms 40540 KB Correct
39 Correct 22 ms 40408 KB Correct
40 Correct 29 ms 40532 KB Correct
41 Correct 21 ms 39532 KB Correct
42 Correct 19 ms 39840 KB Correct
43 Correct 24 ms 40236 KB Correct
44 Correct 22 ms 40536 KB Correct
45 Correct 21 ms 40280 KB Correct
46 Correct 21 ms 40540 KB Correct
47 Correct 20 ms 40288 KB Correct
48 Correct 20 ms 39848 KB Correct
49 Correct 18 ms 39840 KB Correct
50 Correct 20 ms 39852 KB Correct
51 Runtime error 341 ms 302368 KB Execution killed with signal 11
52 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 75820 KB Correct
2 Correct 114 ms 73868 KB Correct
3 Correct 106 ms 68432 KB Correct
4 Correct 79 ms 68744 KB Correct
5 Correct 119 ms 76044 KB Correct
6 Correct 123 ms 75480 KB Correct
7 Correct 134 ms 71596 KB Correct
8 Correct 97 ms 76780 KB Correct
9 Correct 96 ms 77240 KB Correct
10 Correct 76 ms 75876 KB Correct
11 Correct 91 ms 75704 KB Correct
12 Correct 117 ms 75732 KB Correct
13 Correct 105 ms 73916 KB Correct
14 Correct 108 ms 68280 KB Correct
15 Correct 70 ms 68660 KB Correct
16 Correct 98 ms 76048 KB Correct
17 Correct 135 ms 75700 KB Correct
18 Correct 117 ms 71608 KB Correct
19 Correct 107 ms 76700 KB Correct
20 Correct 83 ms 77240 KB Correct
21 Correct 98 ms 75968 KB Correct
22 Correct 72 ms 75756 KB Correct
23 Runtime error 110 ms 136888 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4-3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 76696 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -