Advertisement
a_chn

Untitled

Mar 2nd, 2024
1,263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll> pii;
  5. # define im INT_MAX
  6. # define umap unordered_map
  7. # define uset unordered_set
  8. # define f first
  9. # define s second
  10. # define pq priority_queue
  11. # define pb push_back
  12. # define ins insert
  13. # define INF LLONG_MAX
  14. #define int long long
  15.  
  16. vector<pii> instructions1, instructions2;
  17. vector<array<int,3>> x_sums_1;
  18. map<pair<int, int>,map<int, int>> x_sums_2;
  19. int num_valid_subsets[41];
  20.  
  21. int num_instructions_1=0; int curr_x_sum_1=0; int curr_y_sum_1=0;
  22. void gen_list1(int i){
  23.     if (i==instructions1.size()){
  24.         x_sums_1.pb({curr_x_sum_1,curr_y_sum_1,num_instructions_1});
  25.         return;
  26.     }
  27.     curr_x_sum_1+=instructions1[i].f; curr_y_sum_1+=instructions1[i].s;
  28.     num_instructions_1++; gen_list1(i+1);
  29.     curr_x_sum_1-=instructions1[i].f; curr_y_sum_1-=instructions1[i].s;
  30.     num_instructions_1--; gen_list1(i+1);
  31. }
  32.  
  33. int num_instructions_2=0; int curr_x_sum_2=0; int curr_y_sum_2=0;
  34. void gen_list2(int i){
  35.     if (i==instructions2.size()){
  36.         x_sums_2[{curr_x_sum_2,curr_y_sum_2}][num_instructions_2]++;
  37.         return;
  38.     }
  39.     curr_x_sum_2+=instructions2[i].f; curr_y_sum_2+=instructions2[i].s;
  40.     num_instructions_2++; gen_list2(i+1);
  41.     curr_x_sum_2-=instructions2[i].f; curr_y_sum_2-=instructions2[i].s;
  42.     num_instructions_2--; gen_list2(i+1);
  43. }
  44.  
  45. main(){
  46.     // ifstream cin("triangles.in");
  47.     // ofstream cout("triangles.out");
  48.  
  49.     int n; cin >> n; int xg, yg; cin >> xg >> yg;
  50.     for (int i=0; i<n/2; i++){
  51.         int x, y; cin >> x >> y;
  52.         instructions1.pb({x,y});
  53.     } for (int i=n/2; i<n; i++){
  54.         int x, y; cin >> x >> y;
  55.         instructions2.pb({x,y});
  56.     }
  57.  
  58.     // printContPair(instructions1); printContPair(instructions2);
  59.  
  60.  
  61.     gen_list1(0); gen_list2(0);
  62.  
  63.     for (auto element1 : x_sums_1){ // element from list 1 (x)
  64.         for(auto[num, ways] : x_sums_2[{xg - element1[0], yg - element1[1]}]) {
  65.             num_valid_subsets[element1[2] + num] += ways;
  66.         }
  67.     }
  68.  
  69.  
  70.  
  71.     for (int k=1; k<=n; k++){
  72.         cout << num_valid_subsets[k] << '\n';
  73.     }
  74.  
  75.  
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement