oj.uz

Submission #930427

# Submission time Handle Problem Language Result Execution time Memory
930427 2024-02-19T15:25:13 Z boris_mihov Event Hopping 2 (JOI21_event2) C++17
1 / 100
 3000 ms 1116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 3008 ms 1116 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 8 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 7 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 11 ms 348 KB Output is correct
20 Correct 13 ms 472 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 3 ms 348 KB Output is correct
25 Correct 3 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 8 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 7 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 11 ms 348 KB Output is correct
20 Correct 13 ms 472 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 3 ms 348 KB Output is correct
25 Correct 3 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Incorrect 37 ms 348 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 3008 ms 1116 KB Time limit exceeded
5 Halted 0 ms 0 KB -