fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define eb emplace_back
  6. #define pii pair <int, int>
  7. #define pli pair <ll, int>
  8. #define fi first
  9. #define se second
  10. #define all(ac) ac.begin(), ac.end()
  11. #define MASK(x) (1 << x)
  12. #define ub(i, j) ((i >> j) & 1)
  13. #define FBIT(x) (MASK(x) - 1)
  14. #define FLIP(x, y) (FBIT(x) ^ y)
  15. #define ii make_pair
  16. #define int128 __int128_t
  17.  
  18. struct Vec {
  19.     ll x, y, z;
  20.     int id;
  21. };
  22.  
  23. int32_t main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(0), cout.tie(0);
  26.     #define task "tet"
  27.     if(fopen(task".inp", "r")) {
  28.         freopen(task".inp", "r", stdin);
  29.         freopen(task".out", "w", stdout);
  30.     }
  31.  
  32.     int n;
  33.     ll X, Y, Z;
  34.     cin >> n >> X >> Y >> Z;
  35.  
  36.     vector<Vec> v(n);
  37.     // Nhận diện subtask 1 chiều (Quy hoạch động)
  38.     bool is1D_X = (Y == 0 && Z == 0);
  39.     bool is1D_Y = (X == 0 && Z == 0);
  40.     bool is1D_Z = (X == 0 && Y == 0);
  41.  
  42.     for (int i = 0; i < n; i++) {
  43.         cin >> v[i].x >> v[i].y >> v[i].z;
  44.         v[i].id = i;
  45.         if (v[i].y != 0 || v[i].z != 0) is1D_X = false;
  46.         if (v[i].x != 0 || v[i].z != 0) is1D_Y = false;
  47.         if (v[i].x != 0 || v[i].y != 0) is1D_Z = false;
  48.     }
  49.  
  50.     string ans(n, '0');
  51.  
  52.     // Giải bằng Knapsack + Bitset cho các test 1D
  53.     if (is1D_X) {
  54.         vector<bitset<1000005>> dp(n + 1);
  55.         dp[0][0] = 1;
  56.         for (int i = 0; i < n; i++) dp[i + 1] = dp[i] | (dp[i] << v[i].x);
  57.         ll cur = X;
  58.         for (int i = n - 1; i >= 0; i--) {
  59.             if (cur >= v[i].x && dp[i][cur - v[i].x]) {
  60.                 ans[v[i].id] = '1';
  61.                 cur -= v[i].x;
  62.             }
  63.         }
  64.         cout << ans << "\n";
  65.         return 0;
  66.     }
  67.  
  68.     if (is1D_Y) {
  69.         vector<bitset<1000005>> dp(n + 1);
  70.         dp[0][0] = 1;
  71.         for (int i = 0; i < n; i++) dp[i + 1] = dp[i] | (dp[i] << v[i].y);
  72.         ll cur = Y;
  73.         for (int i = n - 1; i >= 0; i--) {
  74.             if (cur >= v[i].y && dp[i][cur - v[i].y]) {
  75.                 ans[v[i].id] = '1';
  76.                 cur -= v[i].y;
  77.             }
  78.         }
  79.         cout << ans << "\n";
  80.         return 0;
  81.     }
  82.  
  83.     if (is1D_Z) {
  84.         vector<bitset<1000005>> dp(n + 1);
  85.         dp[0][0] = 1;
  86.         for (int i = 0; i < n; i++) dp[i + 1] = dp[i] | (dp[i] << v[i].z);
  87.         ll cur = Z;
  88.         for (int i = n - 1; i >= 0; i--) {
  89.             if (cur >= v[i].z && dp[i][cur - v[i].z]) {
  90.                 ans[v[i].id] = '1';
  91.                 cur -= v[i].z;
  92.             }
  93.         }
  94.         cout << ans << "\n";
  95.         return 0;
  96.     }
  97.  
  98.     // Giải bằng Backtracking + Pruning cho trường hợp 3D tổng quát
  99.     sort(v.begin(), v.end(), [](const Vec& a, const Vec& b) {
  100.         return a.x + a.y + a.z > b.x + b.y + b.z;
  101.     });
  102.  
  103.     vector<ll> sufX(n + 1, 0), sufY(n + 1, 0), sufZ(n + 1, 0);
  104.     for (int i = n - 1; i >= 0; i--) {
  105.         sufX[i] = sufX[i + 1] + v[i].x;
  106.         sufY[i] = sufY[i + 1] + v[i].y;
  107.         sufZ[i] = sufZ[i + 1] + v[i].z;
  108.     }
  109.  
  110.     bool found = false;
  111.     auto dfs = [&](auto& self, int idx, ll cx, ll cy, ll cz) -> void {
  112.         if (found) return;
  113.         if (cx == X && cy == Y && cz == Z) {
  114.             found = true;
  115.             return;
  116.         }
  117.         if (idx == n) return;
  118.         // Nhánh cận: Nếu đã vượt quá mục tiêu
  119.         if (cx > X || cy > Y || cz > Z) return;
  120.         // Nhánh cận: Nếu cộng tất cả phần tử còn lại vẫn không đủ mục tiêu
  121.         if (cx + sufX[idx] < X || cy + sufY[idx] < Y || cz + sufZ[idx] < Z) return;
  122.  
  123.         ans[v[idx].id] = '1';
  124.         self(self, idx + 1, cx + v[idx].x, cy + v[idx].y, cz + v[idx].z);
  125.         if (found) return;
  126.  
  127.         ans[v[idx].id] = '0';
  128.         self(self, idx + 1, cx, cy, cz);
  129.     };
  130.  
  131.     dfs(dfs, 0, 0, 0, 0);
  132.  
  133.     cout << ans << "\n";
  134.  
  135.     return 0;
  136. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
3 1 2 3
1 1 1
1 0 1
0 1 2
stdout
copy 
101
https://ideone.com/SuQWZL
language:
C++ (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!