oj.uz

Submission #972069

# Submission time Handle Problem Language Result Execution time Memory
972069 2024-04-30T02:44:16 Z huutuan Event Hopping 2 (JOI21_event2) C++14
1 / 100
 3000 ms 7500 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10, LG=18;
int n, k;
int l[N], r[N];
vector<int> vv[N];
int jump[LG][N];

int get(int l, int r){
   int ans=0;
   for (int k=LG-1; k>=0; --k){
      if (jump[k][l]<=r){
         ans+=1<<k;
         l=jump[k][l];
      }
   }
   return ans;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> k;
   for (int i=1; i<=n; ++i) cin >> l[i] >> r[i];
   for (int i=(1<<n)-1; i>=0; --i) if (__builtin_popcount(i)==k){
      bool check=1;
      for (int j=0; j<n; ++j) if (i>>(n-j-1)&1) for (int t=j+1; t<n; ++t) if (i>>(n-t-1)&1){
         if (max(l[j+1], l[t+1])<min(r[j+1], r[t+1])){
            check=0;
         }
      }
      if (check){
         for (int j=0; j<n; ++j) if (i>>(n-j-1)&1) cout << j+1 << '\n';
         return 0;
      }
   }
   cout << -1 << '\n';
   return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Execution timed out 3091 ms 7500 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6580 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 61 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 2 ms 6752 KB Output is correct
15 Correct 5 ms 6744 KB Output is correct
16 Correct 29 ms 6748 KB Output is correct
17 Correct 5 ms 6744 KB Output is correct
18 Correct 2 ms 6744 KB Output is correct
19 Correct 32 ms 6748 KB Output is correct
20 Correct 60 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 4 ms 6768 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 4 ms 6748 KB Output is correct
25 Correct 3 ms 6748 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Correct 1 ms 6756 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6580 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 4 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Correct 61 ms 6748 KB Output is correct
12 Correct 3 ms 6748 KB Output is correct
13 Correct 3 ms 6748 KB Output is correct
14 Correct 2 ms 6752 KB Output is correct
15 Correct 5 ms 6744 KB Output is correct
16 Correct 29 ms 6748 KB Output is correct
17 Correct 5 ms 6744 KB Output is correct
18 Correct 2 ms 6744 KB Output is correct
19 Correct 32 ms 6748 KB Output is correct
20 Correct 60 ms 6748 KB Output is correct
21 Correct 2 ms 6748 KB Output is correct
22 Correct 4 ms 6768 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 4 ms 6748 KB Output is correct
25 Correct 3 ms 6748 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Correct 1 ms 6756 KB Output is correct
28 Incorrect 33 ms 6748 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Execution timed out 3091 ms 7500 KB Time limit exceeded
5 Halted 0 ms 0 KB -