Submission #198086

#	Time	Username	Problem	Language	Result	Execution time	Memory
198086		model_code	Restore Array (RMI19_restore)	C++17	38 / 100	8 ms	632 KiB

restore

/**
* user:  apostol-c2d
* fname: Daniel
* lname: Apostol
* task:  restore
* score: 38.0
* date:  2019-10-10 07:05:21.936867
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define get_here cerr << "-1\n"
#define dbg(x) cerr << #x << " " << x << "\n"

int n, m;
const int N = 5000, M = 1e4;
int ans[1 + N];
int k[1 + M];
int val[1 + M];
int l[1 + M];
int r[1 + M];

void fail () {
    cout << "-1\n";
    exit (0);
}


int main () {
    //freopen ("restore.in", "r", stdin);
    //freopen ("restore.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        ans[i] = -1;
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i] >> k[i] >> val[i];
        l[i]++;
        r[i]++;
        if (val[i] == 1 && k[i] == 1) {
            for (int j = l[i]; j <= r[i]; j++) {
                if (ans[j] == 0)
                    fail ();
                ans[j] = 1;
            }
        }
        if (val[i] == 0 && k[i] == r[i] - l[i] + 1) {
            for (int j = l[i]; j <= r[i]; j++) {
                if (ans[j] == 1)
                    fail ();
                ans[j] = 0;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        if (val[i] == 0 && k[i] == 1) {
            bool ok = false;
            for (int j = l[i]; j <= r[i]; j++)
                if (ans[j] != 1) {
                    ok = true;
                    ans[j] = 0;
                    break;
                }
            if (!ok) {
                fail ();
            }
        }
        if (val[i] == 1 && k[i] == r[i] - l[i] + 1) {
            bool ok = false;
            for (int j = l[i]; j <= r[i]; j++)
                if (ans[j] != 0) {
                    ok = true;
                    ans[j] = 1;
                    break;
                }
            if (!ok) {
                fail ();
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i] == -1)
            ans[i] = 0;
        cout << ans[i] << " ";
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55