Submission #930427

#	Time	Username	Problem	Language	Result	Execution time	Memory
930427		boris_mihov	Event Hopping 2 (JOI21_event2)	C++17	1 / 100	3008 ms	1116 KiB

event2

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 2e9;

int n, k;
int l[MAXN];
int r[MAXN];

bool intersecting(int x, int y)
{
    return std::max(l[x], l[y]) < std::min(r[x], r[y]);
}

void solve()
{
    std::vector <int> sol;
    for (int mask = (1 << n) - 1 ; mask >= 0 ; --mask)
    {
        if (__builtin_popcount(mask) != k)
        {
            continue;
        }   

        bool isGood = true;
        for (int i = 0 ; i < n && isGood ; ++i)
        {
            for (int j = i + 1 ; j < n && isGood ; ++j)
            {
                if ((mask & (1 << i)) && (mask & (1 << j)) && intersecting(n - i, n - j))
                {
                    isGood = false;
                }
            }
        }

        if (isGood)
        {
            for (int i = n - 1 ; i >= 0 ; --i)
            {
                if (mask & (1 << i))
                {
                    sol.push_back(n - i);
                }
            }

            break;
        }
    }

    if (sol.empty())
    {
        std::cout << -1 << '\n';
        return;
    }

    for (const int &idx : sol)
    {
        std::cout << idx << '\n';
    }
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
        // l[i]++;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 1 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61