fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define ld long double
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define tiii tuple<int,int,int>
  9. #define tlll tuple<ll,ll,ll>
  10. #define matrix vector<vector<int>>
  11. #define el "\n"
  12. #define pro "chemistry"
  13. #define pb push_back
  14. #define ins insert
  15. #define ii make_pair
  16. #define iii make_tuple
  17. #define fi first
  18. #define se second
  19. #define PI (ld)(acos(-1.0))
  20. #define OO (ll)(1e18+7)
  21. #define oo (int)(5e3+7)
  22. #define mmax (int)(2e5+5)
  23. #define nmax (int)(1e6+7)
  24. #define mod (ll)(1e9+7)
  25.  
  26. void inline Nhap(ll &x){
  27.     char c=getchar();
  28.     ll sign=1;
  29.     x=0;
  30.     while(c<'0'||c>'9'){
  31.         if(c=='-') sign*=-1;
  32.         c=getchar();
  33.     }
  34.     x=c-'0';
  35.     c=getchar();
  36.     while('0'<=c&&c<='9'){
  37.         x=x*10+(c-'0');
  38.         c=getchar();
  39.     }
  40.     x*=sign;
  41. }
  42.  
  43. void inline Xuat(ll x){
  44.     if(x<10){
  45.         putchar('0'+x);
  46.         return;
  47.     }
  48.     Xuat(x/10);
  49.     putchar('0'+x%10);
  50. }
  51.  
  52. static bitset<1024> dp[205][1024];
  53. static bitset<1024> mask_zero[10],mask_one[10];
  54.  
  55. inline bitset<1024> xor_permute(bitset<1024> bs,int v){
  56.     for(int k=0;k<10;k++){
  57.         if(((v>>k)&1)==0) continue;
  58.         bitset<1024> z=bs&mask_zero[k];
  59.         bitset<1024> o=bs&mask_one[k];
  60.         z<<=(1<<k);
  61.         o>>=(1<<k);
  62.         bs=(z|o);
  63.     }
  64.     return bs;
  65. }
  66.  
  67. int main(){
  68.     ios_base::sync_with_stdio(false);
  69.     cin.tie(nullptr);
  70.     cout.tie(nullptr);
  71.     if(fopen(pro".inp","r")){
  72.         freopen(pro".inp","r",stdin);
  73.         freopen(pro".out","w",stdout);
  74.     }
  75.     for(int k=0;k<10;k++){
  76.         for(int i=0;i<1024;i++){
  77.             if(((i>>k)&1)==0) mask_zero[k].set(i);
  78.             else mask_one[k].set(i);
  79.         }
  80.     }
  81.     int t_subtask;
  82.     while(true){
  83.         if(!(cin>>t_subtask)) return 0;
  84.         if(t_subtask==0) break;
  85.         for(int _=0;_<7;_++){
  86.             int n;cin>>n;
  87.             if(n==0) break;
  88.             vector<int> vs(n);
  89.             for(int i=0;i<n;i++) cin>>vs[i];
  90.             for(int a=0;a<1024;a++) dp[0][a].reset();
  91.             dp[0][0].set(0);
  92.             for(int i=1;i<=n;i++){
  93.                 int v=vs[i-1];
  94.                 for(int a=0;a<1024;a++) dp[i][a].reset();
  95.                 for(int a_val=0;a_val<1024;a_val++){
  96.                     const bitset<1024> &bits=dp[i-1][a_val];
  97.                     if(bits.none()) continue;
  98.                     dp[i][a_val]|=bits;
  99.                     int a1=a_val^v;
  100.                     dp[i][a1]|=bits;
  101.                     bitset<1024> perm=xor_permute(bits,v);
  102.                     dp[i][a_val]|=perm;
  103.                 }
  104.             }
  105.             int S_all=0;
  106.             for(int x:vs) S_all^=x;
  107.             static bitset<1024> best_dp[1024];
  108.             for(int a=0;a<1024;a++) best_dp[a]=dp[n][a];
  109.             int bestA=0,bestB=0;
  110.             long long bestSum;
  111.             while(true){
  112.                 bestSum=-1;
  113.                 bestA=bestB=0;
  114.                 for(int a=0;a<1024;a++){
  115.                     const bitset<1024> &bs=best_dp[a];
  116.                     if(bs.none()) continue;
  117.                     for(int b=0;b<1024;b++){
  118.                         if(!bs.test(b)) continue;
  119.                         int c=S_all^a^b;
  120.                         long long s=(long long)a+b+c;
  121.                         if(s>bestSum){
  122.                             bestSum=s;
  123.                             bestA=a;
  124.                             bestB=b;
  125.                         }
  126.                     }
  127.                 }
  128.                 vector<int> assign(n,0);
  129.                 int A=bestA,B=bestB;
  130.                 for(int i=n;i>=1;i--){
  131.                     int v=vs[i-1];
  132.                     if(dp[i-1][A].test(B)){
  133.                         assign[i-1]=3;
  134.                         continue;
  135.                     }
  136.                     int A1=A^v;
  137.                     if(dp[i-1][A1].test(B)){
  138.                         assign[i-1]=1;
  139.                         A=A1;
  140.                         continue;
  141.                     }
  142.                     int B1=B^v;
  143.                     assign[i-1]=2;
  144.                     B=B1;
  145.                 }
  146.                 int cnt1=0,cnt2=0,cnt3=0;
  147.                 for(int x:assign){
  148.                     if(x==1) cnt1++;
  149.                     else if(x==2) cnt2++;
  150.                     else cnt3++;
  151.                 }
  152.                 if(cnt1>0&&cnt2>0&&cnt3>0){
  153.                     string res;
  154.                     res.reserve(n);
  155.                     for(int x:assign){
  156.                         if(x==1) res.push_back('P');
  157.                         else if(x==2) res.push_back('V');
  158.                         else res.push_back('H');
  159.                     }
  160.                     cout<<res<<el;
  161.                     break;
  162.                 }
  163.                 best_dp[bestA].reset(bestB);
  164.             }
  165.         }
  166.     }
  167.     return 0;
  168. }
  169.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mociN4
language:
C++14 (clang 8.0)
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!