Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<ll,ll> pii;
- # define im INT_MAX
- # define umap unordered_map
- # define uset unordered_set
- # define f first
- # define s second
- # define pq priority_queue
- # define pb push_back
- # define ins insert
- # define INF LLONG_MAX
- #define int long long
- vector<pii> instructions1, instructions2;
- vector<array<int,3>> x_sums_1;
- map<pair<int, int>,map<int, int>> x_sums_2;
- int num_valid_subsets[41];
- int num_instructions_1=0; int curr_x_sum_1=0; int curr_y_sum_1=0;
- void gen_list1(int i){
- if (i==instructions1.size()){
- x_sums_1.pb({curr_x_sum_1,curr_y_sum_1,num_instructions_1});
- return;
- }
- curr_x_sum_1+=instructions1[i].f; curr_y_sum_1+=instructions1[i].s;
- num_instructions_1++; gen_list1(i+1);
- curr_x_sum_1-=instructions1[i].f; curr_y_sum_1-=instructions1[i].s;
- num_instructions_1--; gen_list1(i+1);
- }
- int num_instructions_2=0; int curr_x_sum_2=0; int curr_y_sum_2=0;
- void gen_list2(int i){
- if (i==instructions2.size()){
- x_sums_2[{curr_x_sum_2,curr_y_sum_2}][num_instructions_2]++;
- return;
- }
- curr_x_sum_2+=instructions2[i].f; curr_y_sum_2+=instructions2[i].s;
- num_instructions_2++; gen_list2(i+1);
- curr_x_sum_2-=instructions2[i].f; curr_y_sum_2-=instructions2[i].s;
- num_instructions_2--; gen_list2(i+1);
- }
- main(){
- // ifstream cin("triangles.in");
- // ofstream cout("triangles.out");
- int n; cin >> n; int xg, yg; cin >> xg >> yg;
- for (int i=0; i<n/2; i++){
- int x, y; cin >> x >> y;
- instructions1.pb({x,y});
- } for (int i=n/2; i<n; i++){
- int x, y; cin >> x >> y;
- instructions2.pb({x,y});
- }
- // printContPair(instructions1); printContPair(instructions2);
- gen_list1(0); gen_list2(0);
- for (auto element1 : x_sums_1){ // element from list 1 (x)
- for(auto[num, ways] : x_sums_2[{xg - element1[0], yg - element1[1]}]) {
- num_valid_subsets[element1[2] + num] += ways;
- }
- }
- for (int k=1; k<=n; k++){
- cout << num_valid_subsets[k] << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement