Submission #853510

#	Time	Username	Problem	Language	Result	Execution time	Memory
853510		lolismek	Restore Array (RMI19_restore)	C++14	100 / 100	557 ms	41260 KiB

restore

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

#define pii pair <int, int>

using namespace std;

const int NMAX = 5001;
const int INF = 1e9 + 1;

vector <pii> adj[NMAX + 1];

int d[NMAX + 1];

bool inq[NMAX + 1];
int f[NMAX + 1];

int ans[NMAX + 1];

int main(){

    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        int l, r, k, v;
        cin >> l >> r >> k >> v;
        ++l, ++r;

        int a, b, c;

        if(v == 1){
            a = r, b = l - 1, c = -((r - l + 1) - k + 1);
        }else{
            a = l - 1, b = r, c = (r - l + 1) - k;
        }
        adj[a].push_back({b, c});
    }

    for(int i = 0; i <= n; i++){
        d[i] = INF;
    }

    int source = 0;

    for(int i = n; i >= 1; i--){
        adj[i].push_back({i - 1, 0});
        adj[i - 1].push_back({i, 1});
    }

    queue <int> Q;
    Q.push(source);
    d[source] = 0;
    inq[source] = true;

    while(!Q.empty()){
        int node = Q.front();
        Q.pop();

        inq[node] = false;

        if(++f[node] > n){
            cout << -1 << '\n';
            exit(0);
        }

        for(pii vec : adj[node]){
            if(d[node] + vec.second < d[vec.first]){
                
                d[vec.first] = d[node] + vec.second;
                if(!inq[vec.first]){
                    Q.push(vec.first);
                }
            }
        }
    }

    vector <pii> aux;
    for(int i = 1; i <= n; i++){
        if(d[i] != INF){
            aux.push_back({i, d[i]});
        }
    }

    sort(aux.begin(), aux.end());

    int mini = INF;
    for(int i = 0; i <= n; i++){
        mini = min(mini, d[i]);
    }

    for(int i = (int)aux.size() - 1; i >= 0; i--){
        int r = aux[i].second;
        int sz = aux[i].first;
        if(i > 0){
            r -= aux[i - 1].second;
            sz -= aux[i - 1].first;
        }

        if(r > sz){
            cout << -1 << '\n';
            exit(0);
        }

        for(int j = aux[i].first; r > 0; j--, r--){
            ans[j] = 1;
        }
    }

    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }
    cout << '\n';
   

    return 0;
}

/*
5 1
0 4 3 1
*/

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