oj.uz

Submission #238358

# Submission time Handle Problem Language Result Execution time Memory
238358 2020-06-10T21:37:57 Z Sorting Restore Array (RMI19_restore) C++14
13 / 100
 13 ms 1024 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_N = 5000 + 3;
const int k_M = 10000 + 3;

struct Constraint{
    int l, r, k, value;

    Constraint(){}
    Constraint(int l, int r, int k, int value){
        this->l = l;
        this->r = r;
        this->k = k;
        this->value = value;
    }
};

int n, m;
int a[k_N];
Constraint c[k_M];

int prefix[k_N];

int get_count_ones(int l, int r){
    if(l == 0)
        return prefix[r];
    return prefix[r] - prefix[l - 1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for(int i = 0; i < m; ++i)
        cin >> c[i].l >> c[i].r >> c[i].k >> c[i].value;

    for(int i = 0; i < n; ++i)
        a[i] = -1;

    vector<Constraint> new_c;
    for(int i = 0; i < m; ++i){
        auto [l, r, k, value] = c[i];

        if(k == 1 && value == 1){
            for(int j = l; j <= r; ++j)
                a[j] = 1;
        }
        else if(k == (r - l + 1) && value == 0){
            for(int j = l; j <= r; ++j)
                a[j] = 0;
        }
        else
            new_c.push_back(c[i]);
    }

    sort(new_c.begin(), new_c.end(), [](const Constraint &lvalue, const Constraint &rvalue){
        if(lvalue.r - lvalue.l != rvalue.r - rvalue.l)
            return (lvalue.r - lvalue.l) < (rvalue.r - rvalue.l);
        return lvalue.l < rvalue.l;
    });

    for(auto [l, r, k, value]: new_c){
        bool ok = false;
        for(int i = l; i <= r; ++i){
            if(a[i] == value){
                ok = true;
                break;
            }
        }

        if(ok)
            continue;

        for(int i = l; i <= r; ++i){
            if(a[i] == -1){
                a[i] = value;
                ok = true;
                break;
            }
        }

        if(!ok){
            cout << "-1\n";
            return 0;
        }
    }

    for(int i = 0; i < n; ++i)
        a[i] = (a[i] == -1) ? 0 : a[i];

    prefix[0] = 0;
    for(int i = 1; i < n; ++i)
        prefix[i] = prefix[i - 1] + a[i];

    for(int i = 0; i < m; ++i){
        int count_ones = get_count_ones(c[i].l, c[i].r);
        int count_zeros = (c[i].r - c[i].l + 1) - count_ones;

        if(c[i].value == 0 && count_zeros >= c[i].k)
            continue;
        if(c[i].value == 1 && count_zeros < c[i].k)
            continue;

        cout << "-1\n";
        return 0;
    }

    for(int i = 0; i < n; ++i)
        cout << a[i] << " ";
    cout << "\n";
}

Compilation message

restore.cpp: In function 'int main()':
restore.cpp:46:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [l, r, k, value] = c[i];
              ^
restore.cpp:66:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [l, r, k, value]: new_c){
              ^
restore.cpp:66:29: warning: unused variable 'k' [-Wunused-variable]
     for(auto [l, r, k, value]: new_c){
                             ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1024 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1024 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 9 ms 1024 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 9 ms 1024 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 10 ms 1024 KB Output is correct
11 Correct 13 ms 896 KB Output is correct
12 Correct 10 ms 896 KB Output is correct
13 Correct 10 ms 1024 KB Output is correct
14 Incorrect 10 ms 1024 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -