Advertisement
pypcdev

Untitled

Jul 28th, 2021
877
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.09 KB | None | 0 0
  1. //                         _
  2. //   _ __ ___    __ _   __| |  ___
  3. //  | '_ ` _ \  / _` | / _` | / _ \
  4. //  | | | | | || (_| || (_| ||  __/
  5. //  |_| |_| |_| \__,_| \__,_| \___|
  6. //
  7. //   _
  8. //  | |__   _   _
  9. //  | '_ \ | | | |
  10. //  | |_) || |_| |
  11. //  |_.__/  \__, |
  12. //          |___/
  13. //                                  _
  14. //   _ __   _   _  _ __    ___   __| |  ___ __   __
  15. //  | '_ \ | | | || '_ \  / __| / _` | / _ \\ \ / /
  16. //  | |_) || |_| || |_) || (__ | (_| ||  __/ \ V /
  17. //  | .__/  \__, || .__/  \___| \__,_| \___|  \_/
  18. //  |_|     |___/ |_|
  19.  
  20.  
  21. // --last hope--
  22. //#pragma GCC optimize("O3")
  23. #pragma GCC optimize("Ofast")
  24. //#pragma GCC optimization("unroll-loops")
  25. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  26.  
  27. #include<bits/stdc++.h>
  28. #include<ext/pb_ds/assoc_container.hpp>
  29. #include<ext/pb_ds/tree_policy.hpp>
  30. using namespace std;
  31. using namespace __gnu_pbds;
  32. typedef long long ll;
  33. typedef unsigned long long ull;
  34. typedef long double ld;
  35. #define int ull
  36. #define fi first
  37. #define se second
  38. #define pb push_back
  39. #define pf push_front
  40. #define ppb pop_back
  41. #define ppf pop_front
  42. #define mkp make_pair
  43. mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
  44. mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
  45. #define rand32 rng32
  46. #define rand64 rng64
  47. template<typename type,typename comp>
  48. using aset=tree<type,null_type,comp,rb_tree_tag,tree_order_statistics_node_update>;// advanced set with order_of_key and find_by_order
  49. // aset<int,less<int>> is set, but aset<int,less_equal<int> is multiset
  50. const pair<int,int>DIR4[4]={{1,0},{-1,0},{0,1},{0,-1}}; // dirs for 4 ways(like in a matrix)
  51.  
  52. bool validf(int up,int left,int down,int right,int i,int ii){
  53.     return up<=i&&i<=down&&left<=ii&&ii<=right;
  54. }
  55.  
  56. // debug tools only
  57. template<typename F,typename S>ostream&operator<<(ostream&output,const pair<F,S>&data){output<<"{"<<data.fi<<","<<data.se<<"}";return output;}
  58. template<typename T>ostream&operator<<(ostream&output,const set<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  59. template<typename T>ostream&operator<<(ostream&output,const aset<T,less<T>>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  60. template<typename T>ostream&operator<<(ostream&output,const aset<T,greater<T>>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  61. template<typename T>ostream&operator<<(ostream&output,const multiset<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  62. template<typename T>ostream&operator<<(ostream&output,const vector<T>&data){if(data.empty())output<<"{}";else{output<<"{"<<*data.begin();for(auto it=next(data.begin());it!=data.end();it++)cout<<","<<*it;output<<"}";}return output;}
  63.  
  64.  
  65.  
  66. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  67. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  68. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  69. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  70. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  71. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  72. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  73. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  74. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  75. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  76. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  77. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  78. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  79. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  80. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  81. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  82. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  83. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  84. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  85. // safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line safe line
  86.  
  87.  
  88.  
  89. ull getnum(string&s){
  90.     ull ans=0;
  91.     for(int i=1;i<=24;i++)ans=ans*3+(s[i]-1);
  92.     return ans;
  93. }
  94.  
  95. string getstr(ull n){
  96.     string ans="*************************";
  97.     for(int i=1;i<=24;i++){
  98.         ans[24-i+1]=n%3+1;
  99.         n/=3;
  100.     }
  101.     return ans;
  102. }
  103.  
  104. bool solved(string&s){
  105.     for(int i=1;i<=6;i++){
  106.         if(s[2*i-1]!=s[2*i]||s[2*i]!=s[2*i-1+12]||s[2*i-1+12]!=s[2*i+12])return 0;
  107.     }
  108.     return 1;
  109. }
  110.  
  111. void rotcube(string&a,int face,int way){
  112.     if(way==2){
  113.         rotcube(a,face,1);
  114.         rotcube(a,face,1);
  115.         rotcube(a,face,1);
  116.         return;
  117.     }
  118.     if(face==1){
  119.         // 1 13 14 2
  120.         // 21 4 16 11 12 19 7 22
  121.         // 21 4 16 11 12 19 7 22
  122.         swap(a[1],a[13]);swap(a[13],a[14]);swap(a[14],a[2]);
  123.         swap(a[21],a[4]);swap(a[4],a[16]);swap(a[16],a[11]);swap(a[11],a[12]);swap(a[12],a[19]);swap(a[19],a[7]);swap(a[7],a[22]);
  124.         swap(a[21],a[4]);swap(a[4],a[16]);swap(a[16],a[11]);swap(a[11],a[12]);swap(a[12],a[19]);swap(a[19],a[7]);swap(a[7],a[22]);
  125.     }
  126.     if(face==2){
  127.         // 3 15 16 4
  128.         // 9 6 18 23 11 13 1 21
  129.         // 9 6 18 23 11 13 1 21
  130.         swap(a[3],a[15]);swap(a[15],a[16]);swap(a[16],a[4]);
  131.         swap(a[9],a[6]);swap(a[6],a[18]);swap(a[18],a[23]);swap(a[23],a[11]);swap(a[11],a[13]);swap(a[13],a[1]);swap(a[1],a[21]);
  132.         swap(a[9],a[6]);swap(a[6],a[18]);swap(a[18],a[23]);swap(a[23],a[11]);swap(a[11],a[13]);swap(a[13],a[1]);swap(a[1],a[21]);
  133.     }
  134.     if(face==3){
  135.         // 5 17 18 6
  136.         // 10 8 20 24 23 15 3 9
  137.         // 10 8 20 24 23 15 3 9
  138.         swap(a[5],a[17]);swap(a[17],a[18]);swap(a[18],a[6]);
  139.         swap(a[10],a[8]);swap(a[8],a[20]);swap(a[20],a[24]);swap(a[24],a[23]);swap(a[23],a[15]);swap(a[15],a[3]);swap(a[3],a[9]);
  140.         swap(a[10],a[8]);swap(a[8],a[20]);swap(a[20],a[24]);swap(a[24],a[23]);swap(a[23],a[15]);swap(a[15],a[3]);swap(a[3],a[9]);
  141.     }
  142.     if(face==4){
  143.         // 7 19 20 8
  144.         // 22 2 14 12 24 17 5 10
  145.         // 22 2 14 12 24 17 5 10
  146.         swap(a[7],a[19]);swap(a[19],a[20]);swap(a[20],a[8]);
  147.         swap(a[22],a[2]);swap(a[2],a[14]);swap(a[14],a[12]);swap(a[12],a[24]);swap(a[24],a[17]);swap(a[17],a[5]);swap(a[5],a[10]);
  148.         swap(a[22],a[2]);swap(a[2],a[14]);swap(a[14],a[12]);swap(a[12],a[24]);swap(a[24],a[17]);swap(a[17],a[5]);swap(a[5],a[10]);
  149.     }
  150.     if(face==5){
  151.         // 9 21 22 10
  152.         // 6 3 4 1 2 7 8 5
  153.         // 6 3 4 1 2 7 8 5
  154.         swap(a[9],a[21]);swap(a[21],a[22]);swap(a[22],a[10]);
  155.         swap(a[6],a[3]);swap(a[3],a[4]);swap(a[4],a[1]);swap(a[1],a[2]);swap(a[2],a[7]);swap(a[7],a[8]);swap(a[8],a[5]);
  156.         swap(a[6],a[3]);swap(a[3],a[4]);swap(a[4],a[1]);swap(a[1],a[2]);swap(a[2],a[7]);swap(a[7],a[8]);swap(a[8],a[5]);
  157.     }
  158.     if(face==6){
  159.         // 11 23 24 12
  160.         // 13 16 15 18 17 20 19 14
  161.         // 13 16 15 18 17 20 19 14
  162.         swap(a[11],a[23]);swap(a[23],a[24]);swap(a[24],a[12]);
  163.         swap(a[13],a[16]);swap(a[16],a[15]);swap(a[15],a[18]);swap(a[18],a[17]);swap(a[17],a[20]);swap(a[20],a[19]);swap(a[19],a[14]);
  164.         swap(a[13],a[16]);swap(a[16],a[15]);swap(a[15],a[18]);swap(a[18],a[17]);swap(a[17],a[20]);swap(a[20],a[19]);swap(a[19],a[14]);
  165.     }
  166. }
  167.  
  168. unordered_map<ull,short>path;
  169.  
  170. signed main(){
  171.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  172.     string clr="*************************";
  173.     for(int i=1;i<=24;i++){
  174.         char x;
  175.         cin>>x;
  176.         if(x=='R')clr[i]=1;
  177.         if(x=='G')clr[i]=2;
  178.         if(x=='B')clr[i]=3;
  179.     }
  180.     int n=getnum(clr);
  181.     if(solved(clr)){
  182.         cout<<"Solved\n";
  183.         return 0;
  184.     }
  185.     queue<pair<int,short>>q;
  186.     q.push({n,0});
  187.     path[n]=1;
  188.     while(!q.empty()){
  189.         int k=q.front().fi;
  190.         int d=q.front().se;
  191.         q.pop();
  192.         string c=getstr(k);
  193.         for(int i=1;i<=6;i++){
  194.             for(int ii=1;ii<=2;ii++){
  195.                 string p=c;
  196.                 rotcube(p,i,ii);
  197.                 int kk=getnum(p);
  198.                 if(!path[kk]){
  199.                     if(solved(p)){
  200.                         vector<int>ans;
  201.                         ans.pb(2*i-1+ii-1);
  202.                         string a=getstr(k);
  203.                         int r=k;
  204.                         while(d--){
  205.                             ans.pb(path[r]);
  206.                             int face=(ans.back()+1)/2;
  207.                             rotcube(a,face, ans.back()%2+1);
  208.                             r=getnum(a);
  209.                         }
  210.                         //cout<<ans<<"\n";
  211.                         reverse(ans.begin(),ans.end());
  212.                         for(auto e:ans){
  213.                             if((e+1)/2==1)cout<<'F';
  214.                             if((e+1)/2==2)cout<<'L';
  215.                             if((e+1)/2==3)cout<<'B';
  216.                             if((e+1)/2==4)cout<<'R';
  217.                             if((e+1)/2==5)cout<<'U';
  218.                             if((e+1)/2==6)cout<<'D';
  219.                             if(e%2==1)cout<<"'";
  220.                         }
  221.                         cout<<"\n";
  222.                         return 0;
  223.                     }
  224.                     path[kk]=2*i-1+ii-1;
  225.                     q.push({kk,d+1});
  226.                 }
  227.             }
  228.         }
  229.     }
  230.  
  231. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement