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. struct State {
  24.     ll x, y, z;
  25.     ll mask;
  26.     bool operator<(const State& o) const {
  27.         if (x != o.x) return x < o.x;
  28.         if (y != o.y) return y < o.y;
  29.         return z < o.z;
  30.     }
  31.     bool operator==(const State& o) const {
  32.         return x == o.x && y == o.y && z == o.z;
  33.     }
  34. };
  35.  
  36. int32_t main() {
  37.     ios::sync_with_stdio(false);
  38.     cin.tie(0), cout.tie(0);
  39.     #define task "tet"
  40.     if(fopen(task".inp", "r")) {
  41.         freopen(task".inp", "r", stdin);
  42.         freopen(task".out", "w", stdout);
  43.     }
  44.  
  45.     auto start_time = chrono::high_resolution_clock::now();
  46.  
  47.     int n;
  48.     ll X, Y, Z;
  49.     cin >> n >> X >> Y >> Z;
  50.  
  51.     vector<Vec> v(n);
  52.     bool is1D_X = (Y == 0 && Z == 0);
  53.     bool is1D_Y = (X == 0 && Z == 0);
  54.     bool is1D_Z = (X == 0 && Y == 0);
  55.  
  56.     for (int i = 0; i < n; i++) {
  57.         cin >> v[i].x >> v[i].y >> v[i].z;
  58.         v[i].id = i;
  59.         if (v[i].y != 0 || v[i].z != 0) is1D_X = false;
  60.         if (v[i].x != 0 || v[i].z != 0) is1D_Y = false;
  61.         if (v[i].x != 0 || v[i].y != 0) is1D_Z = false;
  62.     }
  63.  
  64.     string ans(n, '0');
  65.  
  66.     // 1. Xử lý Subtask 1 chiều (Bitset DP)
  67.     if (is1D_X || is1D_Y || is1D_Z) {
  68.         vector<bitset<1000005>> dp(n + 1);
  69.         dp[0][0] = 1;
  70.         ll target = is1D_X ? X : (is1D_Y ? Y : Z);
  71.         for (int i = 0; i < n; i++) {
  72.             ll val = is1D_X ? v[i].x : (is1D_Y ? v[i].y : v[i].z);
  73.             dp[i + 1] = dp[i] | (dp[i] << val);
  74.         }
  75.         ll cur = target;
  76.         for (int i = n - 1; i >= 0; i--) {
  77.             ll val = is1D_X ? v[i].x : (is1D_Y ? v[i].y : v[i].z);
  78.             if (cur >= val && dp[i][cur - val]) {
  79.                 ans[v[i].id] = '1';
  80.                 cur -= val;
  81.             }
  82.         }
  83.         cout << ans << "\n";
  84.         return 0;
  85.     }
  86.  
  87.     // 2. Xử lý N <= 40 (Meet-in-the-Middle)
  88.     if (n <= 40) {
  89.         int n1 = n / 2;
  90.         int n2 = n - n1;
  91.         vector<State> left_states;
  92.         left_states.reserve(MASK(n1));
  93.  
  94.         for (ll mask = 0; mask < MASK(n1); mask++) {
  95.             ll cx = 0, cy = 0, cz = 0;
  96.             for (int i = 0; i < n1; i++) {
  97.                 if (ub(mask, i)) {
  98.                     cx += v[i].x; cy += v[i].y; cz += v[i].z;
  99.                 }
  100.             }
  101.             if (cx <= X && cy <= Y && cz <= Z) {
  102.                 left_states.push_back({cx, cy, cz, mask});
  103.             }
  104.         }
  105.  
  106.         sort(all(left_states));
  107.  
  108.         for (ll mask = 0; mask < MASK(n2); mask++) {
  109.             ll cx = 0, cy = 0, cz = 0;
  110.             for (int i = 0; i < n2; i++) {
  111.                 if (ub(mask, i)) {
  112.                     cx += v[n1 + i].x; cy += v[n1 + i].y; cz += v[n1 + i].z;
  113.                 }
  114.             }
  115.             if (cx <= X && cy <= Y && cz <= Z) {
  116.                 State target = {X - cx, Y - cy, Z - cz, 0};
  117.                 auto it = lower_bound(all(left_states), target);
  118.                 if (it != left_states.end() && *it == target) {
  119.                     for (int i = 0; i < n1; i++) if (ub(it->mask, i)) ans[v[i].id] = '1';
  120.                     for (int i = 0; i < n2; i++) if (ub(mask, i)) ans[v[n1 + i].id] = '1';
  121.                     cout << ans << "\n";
  122.                     return 0;
  123.                 }
  124.             }
  125.         }
  126.     }
  127.  
  128.     // 3. Xử lý 3D tổng quát (Randomized DFS)
  129.     mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  130.     bool found = false;
  131.     vector<ll> sufX(n + 1, 0), sufY(n + 1, 0), sufZ(n + 1, 0);
  132.  
  133.     while (chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start_time).count() < 900) {
  134.         shuffle(all(v), rng);
  135.  
  136.         for (int i = n - 1; i >= 0; i--) {
  137.             sufX[i] = sufX[i + 1] + v[i].x;
  138.             sufY[i] = sufY[i + 1] + v[i].y;
  139.             sufZ[i] = sufZ[i + 1] + v[i].z;
  140.         }
  141.  
  142.         int nodes_visited = 0;
  143.         int max_nodes = 5000; // Giới hạn số lần thử cho mỗi cấu hình shuffle
  144.  
  145.         auto dfs = [&](auto& self, int idx, ll cx, ll cy, ll cz) -> void {
  146.             if (found || nodes_visited > max_nodes) return;
  147.             nodes_visited++;
  148.  
  149.             if (cx == X && cy == Y && cz == Z) {
  150.                 found = true;
  151.                 return;
  152.             }
  153.             if (idx == n) return;
  154.             if (cx > X || cy > Y || cz > Z) return;
  155.             if (cx + sufX[idx] < X || cy + sufY[idx] < Y || cz + sufZ[idx] < Z) return;
  156.  
  157.             ans[v[idx].id] = '1';
  158.             self(self, idx + 1, cx + v[idx].x, cy + v[idx].y, cz + v[idx].z);
  159.             if (found) return;
  160.  
  161.             ans[v[idx].id] = '0';
  162.             self(self, idx + 1, cx, cy, cz);
  163.         };
  164.  
  165.         dfs(dfs, 0, 0, 0, 0);
  166.         if (found) break;
  167.     }
  168.  
  169.     if (found) cout << ans << "\n";
  170.  
  171.     return 0;
  172. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/6c1VK4
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
1 hour 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!