fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 1e6+5;
  11.  
  12. int n, n1, n2, x, y, a[maxN], b[maxN];
  13. int mask1 = -1, mask2 = -1, mask3 = -1, mask4 = -1;
  14. map<int,int>mp, mp2;
  15. int ans[maxN];
  16.  
  17. void backtrack1_a(int pos, int sum, int mask)
  18. {
  19.     if(pos == n1/2+1)
  20.     {
  21.         mp[sum] = mask;
  22.         return;
  23.     }
  24.     else
  25.     {
  26.         backtrack1_a(pos+1, sum-a[pos], mask);
  27.         backtrack1_a(pos+1, sum+a[pos], mask+(1ll<<pos));
  28.     }
  29. }
  30.  
  31. void backtrack2_a(int pos, int sum, int mask)
  32. {
  33.     if(mask1 != -1) return;
  34.     if(pos == n1+1)
  35.     {
  36.         if(!mp.count(y-sum)) return;
  37.         mask1 = mp[y-sum];
  38.         mask2 = mask;
  39.         return;
  40.     }
  41.     else
  42.     {
  43.         backtrack2_a(pos+1, sum-a[pos], mask);
  44.         backtrack2_a(pos+1, sum+a[pos], mask+(1ll<<pos));
  45.     }
  46. }
  47.  
  48. void backtrack1_b(int pos, int sum, int mask)
  49. {
  50.     if(pos == n2/2+1)
  51.     {
  52.         mp2[sum] = mask;
  53.         return;
  54.     }
  55.     else
  56.     {
  57.         backtrack1_b(pos+1, sum-b[pos], mask);
  58.         backtrack1_b(pos+1, sum+b[pos], mask+(1ll<<pos));
  59.     }
  60. }
  61.  
  62. void backtrack2_b(int pos, int sum, int mask)
  63. {
  64.     if(mask3 != -1) return;
  65.     if(pos == n2+1)
  66.     {
  67.         if(!mp2.count(x-sum)) return;
  68.         mask3 = mp2[x-sum];
  69.         mask4 = mask;
  70.         return;
  71.     }
  72.     else
  73.     {
  74.         backtrack2_b(pos+1, sum-b[pos], mask);
  75.         backtrack2_b(pos+1, sum+b[pos], mask+(1ll<<pos));
  76.     }
  77. }
  78. int32_t main()
  79. {
  80.     ios_base::sync_with_stdio(0); cin.tie(0);
  81.     cin>>n>>x>>y;
  82.     for(int i=1; i<=n; i+=1)
  83.     {
  84.         if(i & 1) cin>>a[++n1];
  85.         else cin>>b[++n2];
  86.     }
  87.     backtrack1_a(1, 0, 0);
  88.     backtrack2_a(n1/2+1, 0, 0);
  89.     backtrack1_b(1, 0, 0);
  90.     backtrack2_b(n2/2+1, 0, 0);
  91.     // cout<<mask1<<" "<<mask2<<'\n';
  92.     // cout<<mask3<<" "<<mask4<<'\n';
  93.     if(mask1 == -1 || mask3 == -1)
  94.     {
  95.         cout<<"No"<<'\n'; return 0;
  96.     }
  97.     int tmp1 = 0, tmp2 = 0;
  98.     for(int i=1; i<=n; i+=1)
  99.     {
  100.         if(i & 1)
  101.         {
  102.             tmp1++;
  103.             if((1ll<<tmp1) & mask1 || (1ll<<tmp1) & mask2) ans[i] = 1;
  104.             else ans[i] = -1;
  105.         }
  106.         else
  107.         {
  108.             tmp2++;
  109.             if((1ll<<tmp2) & mask3 || (1ll<<tmp2) & mask4) ans[i] = 1;
  110.             else ans[i] = -1;
  111.         }
  112.     }
  113.     // for(int i=1; i<=n; i+=1) cout<<ans[i]<<" ";
  114.     // int cur_x = 0, cur_y = 0, x1 = 0, x2 = 0;
  115.     // for(int i=1; i<=n; i+=1)
  116.     // {
  117.     //     if(i & 1) cur_x += ans[i] * a[++x1];
  118.     //     else cur_y += ans[i] * b[++x2];
  119.     // }
  120.     // cout<<cur_x<<" "<<cur_y<<'\n';
  121.     cout<<"Yes"<<'\n';
  122.     int cur = 0;
  123.     for(int i=1; i<=n; i+=1)
  124.     {
  125.         int tmp = 0;
  126.         if(i % 2 == 1)
  127.         {
  128.             if(ans[i] == 1) tmp = 1;
  129.             else tmp = 3;
  130.         }
  131.         else
  132.         {
  133.             if(ans[i] == 1) tmp = 0;
  134.             else tmp = 2;
  135.         }
  136.         if(tmp == (cur + 1) % 4) cout<<"L";
  137.         else cout<<"R";
  138.         cur = tmp;
  139.     }
  140. }
  141. // cur = 0 : +x
  142. // cur = 1 : +y
  143. // cur = 2 : -x
  144. // cur = 3 : -y
Success #stdin #stdout 0s 5656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
https://ideone.com/ekCV73
language:
C++14 (gcc 8.3)
created:
1 day 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!