제출 #1131448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131448		huutuan	Card Collection (JOI24_collection)	C++20	11 / 100	178 ms	250928 KiB

Main

#include<bits/stdc++.h>

using namespace std;

int n, m;
int a[20], b[20];
int f[20][20][20][20][20][20];

int dp(int l, int r, int la, int ra, int lb, int rb){
   if (f[l][r][la][ra][lb][rb]!=-1) return f[l][r][la][ra][lb][rb];
   if (l==r) return f[l][r][la][ra][lb][rb]=(la<=a[l] && a[l]<=ra && lb<=b[l] && b[l]<=rb);
   int res=0;
   for (int i=l; i<r; ++i){
      if (dp(l, i, la, ra, lb, rb) && dp(i+1, r, la, n-1, lb, n-1)){ res=1; break; }
      if (dp(l, i, la, ra, lb, n-1) && dp(i+1, r, la, n-1, lb, rb)){ res=1; break; }
      if (dp(l, i, la, n-1, lb, rb) && dp(i+1, r, la, ra, lb, n-1)){ res=1; break; }
      if (dp(l, i, la, n-1, lb, n-1) && dp(i+1, r, la, ra, lb, rb)){ res=1; break; }
      if (dp(l, i, la, ra, lb, rb) && dp(i+1, r, 0, ra, 0, rb)){ res=1; break; }
      if (dp(l, i, la, ra, 0, rb) && dp(i+1, r, 0, ra, lb, rb)){ res=1; break; }
      if (dp(l, i, 0, ra, lb, rb) && dp(i+1, r, la, ra, 0, rb)){ res=1; break; }
      if (dp(l, i, 0, ra, 0, rb) && dp(i+1, r, la, ra, lb, rb)){ res=1; break; }
   }
   return f[l][r][la][ra][lb][rb]=res;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   vector<int> va, vb;
   for (int i=0; i<n; ++i) cin >> a[i] >> b[i], va.push_back(a[i]), vb.push_back(b[i]);
   sort(va.begin(), va.end()); sort(vb.begin(), vb.end());
   va.resize(unique(va.begin(), va.end())-va.begin()); vb.resize(unique(vb.begin(), vb.end())-vb.begin());
   for (int i=0; i<n; ++i) a[i]=lower_bound(va.begin(), va.end(), a[i])-va.begin(), b[i]=lower_bound(vb.begin(), vb.end(), b[i])-vb.begin();
   memset(f, -1, sizeof f);
   for (int i=1; i<=m; ++i){
      int x, y; cin >> x >> y;
      if (binary_search(va.begin(), va.end(), x) && binary_search(vb.begin(), vb.end(), y)){
         x=lower_bound(va.begin(), va.end(), x)-va.begin();
         y=lower_bound(vb.begin(), vb.end(), y)-vb.begin();
         if (dp(0, n-1, x, x, y, y)) cout << i << ' ';
      }
   }
   return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 38
• Subtask 3: 0 / 22
• Subtask 4: 0 / 29