oj.uz

Submission #1072982

# Submission time Handle Problem Language Result Execution time Memory
1072982 2024-08-24T08:00:18 Z edogawa_something Brought Down the Grading Server? (CEOI23_balance) C++17
30 / 100
 450 ms 409288 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++) {
            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 106 ms 191060 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 150 ms 191120 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 144 ms 130996 KB Correct
2 Correct 140 ms 129220 KB Correct
3 Correct 167 ms 123844 KB Correct
4 Correct 105 ms 124692 KB Correct
5 Correct 122 ms 131256 KB Correct
6 Correct 165 ms 130900 KB Correct
7 Correct 161 ms 126904 KB Correct
8 Correct 112 ms 132032 KB Correct
9 Correct 115 ms 132612 KB Correct
10 Correct 106 ms 131144 KB Correct
11 Correct 109 ms 131036 KB Correct

Subtask #2-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 130996 KB Correct
2 Correct 140 ms 129220 KB Correct
3 Correct 167 ms 123844 KB Correct
4 Correct 105 ms 124692 KB Correct
5 Correct 122 ms 131256 KB Correct
6 Correct 165 ms 130900 KB Correct
7 Correct 161 ms 126904 KB Correct
8 Correct 112 ms 132032 KB Correct
9 Correct 115 ms 132612 KB Correct
10 Correct 106 ms 131144 KB Correct
11 Correct 109 ms 131036 KB Correct
12 Correct 169 ms 130996 KB Correct
13 Correct 153 ms 129176 KB Correct
14 Correct 121 ms 123888 KB Correct
15 Correct 109 ms 124556 KB Correct
16 Correct 128 ms 131256 KB Correct
17 Correct 140 ms 130864 KB Correct
18 Correct 152 ms 126904 KB Correct
19 Correct 111 ms 132032 KB Correct
20 Correct 107 ms 132588 KB Correct
21 Correct 102 ms 131100 KB Correct
22 Correct 110 ms 131036 KB Correct
23 Runtime error 180 ms 250040 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 150 ms 191120 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 38 ms 94292 KB Correct
2 Correct 41 ms 96928 KB Correct
3 Correct 44 ms 96624 KB Correct
4 Correct 41 ms 96920 KB Correct
5 Correct 40 ms 95904 KB Correct
6 Correct 45 ms 96148 KB Correct
7 Correct 48 ms 96600 KB Correct
8 Correct 44 ms 96792 KB Correct
9 Correct 44 ms 96520 KB Correct
10 Correct 44 ms 96676 KB Correct
11 Correct 40 ms 96612 KB Correct
12 Correct 40 ms 96156 KB Correct
13 Correct 39 ms 96148 KB Correct
14 Correct 42 ms 96068 KB Correct

Subtask #3-2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94292 KB Correct
2 Correct 41 ms 96928 KB Correct
3 Correct 44 ms 96624 KB Correct
4 Correct 41 ms 96920 KB Correct
5 Correct 40 ms 95904 KB Correct
6 Correct 45 ms 96148 KB Correct
7 Correct 48 ms 96600 KB Correct
8 Correct 44 ms 96792 KB Correct
9 Correct 44 ms 96520 KB Correct
10 Correct 44 ms 96676 KB Correct
11 Correct 40 ms 96612 KB Correct
12 Correct 40 ms 96156 KB Correct
13 Correct 39 ms 96148 KB Correct
14 Correct 42 ms 96068 KB Correct
15 Correct 41 ms 94296 KB Correct
16 Correct 46 ms 96852 KB Correct
17 Correct 60 ms 96720 KB Correct
18 Correct 61 ms 96852 KB Correct
19 Correct 46 ms 95896 KB Correct
20 Correct 55 ms 96104 KB Correct
21 Correct 46 ms 96652 KB Correct
22 Correct 49 ms 96848 KB Correct
23 Correct 39 ms 96596 KB Correct
24 Correct 51 ms 96848 KB Correct
25 Correct 42 ms 96608 KB Correct
26 Correct 42 ms 96164 KB Correct
27 Correct 41 ms 96152 KB Correct
28 Correct 59 ms 96148 KB Correct
29 Runtime error 126 ms 195664 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 38 ms 94292 KB Correct
2 Correct 41 ms 96928 KB Correct
3 Correct 44 ms 96624 KB Correct
4 Correct 41 ms 96920 KB Correct
5 Correct 40 ms 95904 KB Correct
6 Correct 45 ms 96148 KB Correct
7 Correct 48 ms 96600 KB Correct
8 Correct 44 ms 96792 KB Correct
9 Correct 44 ms 96520 KB Correct
10 Correct 44 ms 96676 KB Correct
11 Correct 40 ms 96612 KB Correct
12 Correct 40 ms 96156 KB Correct
13 Correct 39 ms 96148 KB Correct
14 Correct 42 ms 96068 KB Correct
15 Correct 41 ms 94296 KB Correct
16 Correct 46 ms 96852 KB Correct
17 Correct 60 ms 96720 KB Correct
18 Correct 61 ms 96852 KB Correct
19 Correct 46 ms 95896 KB Correct
20 Correct 55 ms 96104 KB Correct
21 Correct 46 ms 96652 KB Correct
22 Correct 49 ms 96848 KB Correct
23 Correct 39 ms 96596 KB Correct
24 Correct 51 ms 96848 KB Correct
25 Correct 42 ms 96608 KB Correct
26 Correct 42 ms 96164 KB Correct
27 Correct 41 ms 96152 KB Correct
28 Correct 59 ms 96148 KB Correct
29 Runtime error 126 ms 195664 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 144 ms 130996 KB Correct
2 Correct 140 ms 129220 KB Correct
3 Correct 167 ms 123844 KB Correct
4 Correct 105 ms 124692 KB Correct
5 Correct 122 ms 131256 KB Correct
6 Correct 165 ms 130900 KB Correct
7 Correct 161 ms 126904 KB Correct
8 Correct 112 ms 132032 KB Correct
9 Correct 115 ms 132612 KB Correct
10 Correct 106 ms 131144 KB Correct
11 Correct 109 ms 131036 KB Correct
12 Correct 38 ms 94292 KB Correct
13 Correct 41 ms 96928 KB Correct
14 Correct 44 ms 96624 KB Correct
15 Correct 41 ms 96920 KB Correct
16 Correct 40 ms 95904 KB Correct
17 Correct 45 ms 96148 KB Correct
18 Correct 48 ms 96600 KB Correct
19 Correct 44 ms 96792 KB Correct
20 Correct 44 ms 96520 KB Correct
21 Correct 44 ms 96676 KB Correct
22 Correct 40 ms 96612 KB Correct
23 Correct 40 ms 96156 KB Correct
24 Correct 39 ms 96148 KB Correct
25 Correct 42 ms 96068 KB Correct
26 Correct 144 ms 130996 KB Correct
27 Correct 149 ms 129108 KB Correct
28 Correct 120 ms 123832 KB Correct
29 Correct 99 ms 124712 KB Correct
30 Correct 152 ms 131256 KB Correct
31 Correct 138 ms 130740 KB Correct
32 Correct 142 ms 126776 KB Correct
33 Correct 141 ms 131916 KB Correct
34 Correct 140 ms 132544 KB Correct
35 Correct 135 ms 131100 KB Correct
36 Correct 140 ms 131000 KB Correct
37 Correct 60 ms 94288 KB Correct
38 Correct 43 ms 97104 KB Correct
39 Correct 43 ms 96624 KB Correct
40 Correct 40 ms 96856 KB Correct
41 Correct 49 ms 95896 KB Correct
42 Correct 48 ms 96152 KB Correct
43 Correct 46 ms 96672 KB Correct
44 Correct 45 ms 96820 KB Correct
45 Correct 43 ms 96440 KB Correct
46 Correct 43 ms 96860 KB Correct
47 Correct 45 ms 96608 KB Correct
48 Correct 43 ms 96116 KB Correct
49 Correct 45 ms 96084 KB Correct
50 Correct 49 ms 96148 KB Correct
51 Correct 433 ms 217416 KB Correct
52 Correct 383 ms 214832 KB Correct
53 Correct 111 ms 118476 KB Correct
54 Correct 162 ms 141892 KB Correct
55 Correct 341 ms 204588 KB Correct
56 Correct 362 ms 215084 KB Correct
57 Correct 450 ms 220704 KB Correct
58 Runtime error 309 ms 409288 KB Execution killed with signal 6
59 Halted 0 ms 0 KB -

Subtask #4-2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 130996 KB Correct
2 Correct 140 ms 129220 KB Correct
3 Correct 167 ms 123844 KB Correct
4 Correct 105 ms 124692 KB Correct
5 Correct 122 ms 131256 KB Correct
6 Correct 165 ms 130900 KB Correct
7 Correct 161 ms 126904 KB Correct
8 Correct 112 ms 132032 KB Correct
9 Correct 115 ms 132612 KB Correct
10 Correct 106 ms 131144 KB Correct
11 Correct 109 ms 131036 KB Correct
12 Correct 169 ms 130996 KB Correct
13 Correct 153 ms 129176 KB Correct
14 Correct 121 ms 123888 KB Correct
15 Correct 109 ms 124556 KB Correct
16 Correct 128 ms 131256 KB Correct
17 Correct 140 ms 130864 KB Correct
18 Correct 152 ms 126904 KB Correct
19 Correct 111 ms 132032 KB Correct
20 Correct 107 ms 132588 KB Correct
21 Correct 102 ms 131100 KB Correct
22 Correct 110 ms 131036 KB Correct
23 Runtime error 180 ms 250040 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 106 ms 191060 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -