ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1303. Минимальное покрытие

If you are having trouble
Послано urmat 9 фев 2020 01:50
There is full solution!!! Try thinking yourself or using hints before watching it
and use visual c++ 2017
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define pb push_back

using namespace std;
const int N = 50000;

pair<int, int> dp[N], right_end[N];
vector<pair<int, int> > v;
vector<int> ans;
unsigned main()
{
    for(int i = 0; i < N; i++)
    {
        right_end[i].first = -50001;
        right_end[i].second = -50001;
    }
    int m;
    cin >> m;
    int l, r;
    int k = 0;
    while(true)
    {
        cin >> l >> r;

        if(l > m || r < 0) continue;

        if(l == 0 && r == 0) break;

        v.pb({l, r});

        if(r > right_end[l].first)
        {
            right_end[l].first = r;
            right_end[l].second = k;
        }
        k++;
    }

    int i = 0;
    for(auto it: v)
    {
        if(it.first <= 0 && it.second > 0)
        {
            if(it.second > dp[0].first)
            {
                dp[0].first = it.second;
                dp[0].second = i;
            }
        }
        i++;
    }
    for(int i = 1; i <= m; i++)
    {
        if(dp[i - 1].first >= right_end[i].first)
        {
            dp[i].first = dp[i - 1].first;
            dp[i].second = dp[i - 1].second;
        } else
        {
            dp[i].first = right_end[i].first;
            dp[i].second = right_end[i].second;
        }
    }
    for(int i = 0; i <= m; i++)
    {
        if(dp[i].first < i)
        {
            cout << "No solution" << endl;
            return 0;
        }
    }
    int pos = 0;
    while(pos < m)
    {
        ans.pb(dp[pos].second);
        if(dp[pos].first == pos)
        {
            cout << "No solution" << endl;
            return 0;
        }
        pos = dp[pos].first;
    }
    cout << ans.size() << endl;
    for(auto it: ans)
    {
        cout << v[(int)it].first << " " << v[(int)it].second << endl;
    }
}

Edited by author 09.02.2020 01:50