Submission #972069

#	Time	Username	Problem	Language	Result	Execution time	Memory
972069		huutuan	Event Hopping 2 (JOI21_event2)	C++14	1 / 100	3091 ms	7500 KiB

event2

#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
• Subtask 2: 1 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61