oj.uz

Submission #1041597

# Submission time Handle Problem Language Result Execution time Memory
1041597 2024-08-02T06:03:35 Z GEN(#11054) Brought Down the Grading Server? (CEOI23_balance) C++17
0 / 100
 2 ms 5208 KB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> A;
int B[100005]; // B[val] = id
int C[100005];
int D[100005]; // D[id] = sum
int E[100005]; // current
int N, S;
vector<int> DnC2(int s, int e, int a, int b) {
    int i, j;
    if(s>=e) return {};
    if(s+1==e) {
        vector<int> v;
        for(i=a;i<b;i++) v.push_back(A[s][i]);
        v.erase(unique(v.begin(),v.end()),v.end());
        return v;
    }
    int mid = (s+e)/2;
    vector<int> v1 = DnC2(s, mid, a, b);
    vector<int> v2 = DnC2(mid, e, a, b);
    vector<int> v;
    v.resize(v1.size()+v2.size());
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v.begin());
    v.erase(unique(v.begin(),v.end()),v.end());
    return v;
}
void DnC(int s, int e) {
    if(e==s+1) return;
    int i, j;
    vector<int> S = DnC2(0, N, s, e);
    int T = S.size();
    for(i=0;i<T;i++) B[S[i]] = i;
    int mid = (s+e)/2;
    for(i=0;i<T;i++) {
        D[i] = 0;
    }
    for(i=0;i<N;i++) {
        for(j=s;j<e;j++) {
            D[B[A[i][j]]]++;
        }
    }
    vector<int> v;
    for(i=0;i<T;i++) {
        if(D[i] % 2 == 0) D[i] = 0;
        else v.push_back(i);
    }
    assert(v.size()%2==0);
    int sz = v.size();
    for(i=0;i<sz/2;i++) D[v[i]] = 1;
    for(i=sz/2;i<sz;i++) D[v[i]] = -1;
    for(i=0;i<T;i++) E[i] = 0;
    for(i=0;i<N;i++) {
        vector<array<int, 4>> V;
        for(j=s;j<e;) {
            int pt = j;
            while(pt+1<e&&A[i][j]==A[i][pt+1]) pt++;
            //[j ~ pt]
            V.push_back({j, pt, A[i][j], -1});
            j = pt + 1;
        }
        vector<array<int, 2>> V2;
        for(j=0;j<V.size();j++) {
            if((V[j][1]-V[j][0]+1)%2==0) {
                V[j][3] = 0;
                continue;
            }
            int n = V[j][2];
            V2.push_back({E[B[n]]-D[B[n]], j});
        }
        sort(V2.begin(),V2.end());
        int sz = V2.size();
        for(j=0;j<sz/2;j++) V[V2[j][1]][3] = 1;
        for(j=sz/2;j<sz;j++) V[V2[j][1]][3] = -1;
        int l = s, r = mid;
        for(auto n : V) {
            int v = n[1] - n[0] + 1;
            int a = -1, b = -1;
            if(n[3]==0) a = v/2, b=v/2;
            if(n[3]==1) a = v/2+1, b = v/2;
            if(n[3]==-1) a = v/2, b = v/2+1;
            E[B[n[2]]] += n[3];
            assert(l+a-1 < mid && r+b-1 < e);
            for(j=l;j<=l+a-1;j++) A[i][j] = n[2];
            l += a;
            for(j=r;j<=r+b-1;j++) A[i][j] = n[2];
            r += b;
        }
        assert(l == mid && r == e);
    }
    for(i=0;i<T;i++) assert(E[i] == D[i]);
    DnC(s, mid);
    DnC(mid, e);
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> N >> S >> T;
    A.resize(N);
    int i, j;
    assert(false);
    for(i=0;i<N;i++) A[i].resize(S);
    for(i=0;i<N;i++) {
        for(j=0;j<S;j++) cin >> A[i][j];
    }
    for(i=0;i<N;i++) sort(A[i].begin(),A[i].end());
    DnC(0, S);
    for(i=0;i<N;i++) {
        for(j=0;j<S;j++)cout << A[i][j] << ' ';
        cout << '\n';
    }
}

Compilation message

balance.cpp: In function 'std::vector<int> DnC2(int, int, int, int)':
balance.cpp:10:12: warning: unused variable 'j' [-Wunused-variable]
   10 |     int i, j;
      |            ^
balance.cpp: In function 'void DnC(int, int)':
balance.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(j=0;j<V.size();j++) {
      |                 ~^~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 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 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2-1
0.0 / 15.0

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

Subtask #2-2
0.0 / 5.0

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

Subtask #2-3
0.0 / 5.0

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

Subtask #3-1
0.0 / 15.0

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

Subtask #3-2
0.0 / 5.0

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

Subtask #3-3
0.0 / 5.0

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

Subtask #4-1
0.0 / 20.0

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

Subtask #4-2
0.0 / 10.0

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

Subtask #4-3
0.0 / 10.0

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