Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // _
- // _ __ ___ __ _ __| | ___
- // | '_ ` _ \ / _` | / _` | / _ \
- // | | | | | || (_| || (_| || __/
- // |_| |_| |_| \__,_| \__,_| \___|
- //
- // _
- // | |__ _ _
- // | '_ \ | | | |
- // | |_) || |_| |
- // |_.__/ \__, |
- // |___/
- // _
- // _ __ _ _ _ __ ___ __| | ___ __ __
- // | '_ \ | | | || '_ \ / __| / _` | / _ \\ \ / /
- // | |_) || |_| || |_) || (__ | (_| || __/ \ V /
- // | .__/ \__, || .__/ \___| \__,_| \___| \_/
- // |_| |___/ |_|
- // --last hope--
- //#pragma GCC optimize("O3")
- #pragma GCC optimize("Ofast")
- //#pragma GCC optimization("unroll-loops")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- #include<ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define int ull
- #define fi first
- #define se second
- #define pb push_back
- #define pf push_front
- #define ppb pop_back
- #define ppf pop_front
- #define mkp make_pair
- mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
- mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
- #define rand32 rng32
- #define rand64 rng64
- template<typename type,typename comp>
- 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
- // aset<int,less<int>> is set, but aset<int,less_equal<int> is multiset
- const pair<int,int>DIR4[4]={{1,0},{-1,0},{0,1},{0,-1}}; // dirs for 4 ways(like in a matrix)
- bool validf(int up,int left,int down,int right,int i,int ii){
- return up<=i&&i<=down&&left<=ii&&ii<=right;
- }
- // debug tools only
- template<typename F,typename S>ostream&operator<<(ostream&output,const pair<F,S>&data){output<<"{"<<data.fi<<","<<data.se<<"}";return output;}
- 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;}
- 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;}
- 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;}
- 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;}
- 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;}
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- // 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
- ull getnum(string&s){
- ull ans=0;
- for(int i=1;i<=24;i++)ans=ans*3+(s[i]-1);
- return ans;
- }
- string getstr(ull n){
- string ans="*************************";
- for(int i=1;i<=24;i++){
- ans[24-i+1]=n%3+1;
- n/=3;
- }
- return ans;
- }
- bool solved(string&s){
- for(int i=1;i<=6;i++){
- 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;
- }
- return 1;
- }
- void rotcube(string&a,int face,int way){
- if(way==2){
- rotcube(a,face,1);
- rotcube(a,face,1);
- rotcube(a,face,1);
- return;
- }
- if(face==1){
- // 1 13 14 2
- // 21 4 16 11 12 19 7 22
- // 21 4 16 11 12 19 7 22
- swap(a[1],a[13]);swap(a[13],a[14]);swap(a[14],a[2]);
- 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]);
- 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]);
- }
- if(face==2){
- // 3 15 16 4
- // 9 6 18 23 11 13 1 21
- // 9 6 18 23 11 13 1 21
- swap(a[3],a[15]);swap(a[15],a[16]);swap(a[16],a[4]);
- 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]);
- 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]);
- }
- if(face==3){
- // 5 17 18 6
- // 10 8 20 24 23 15 3 9
- // 10 8 20 24 23 15 3 9
- swap(a[5],a[17]);swap(a[17],a[18]);swap(a[18],a[6]);
- 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]);
- 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]);
- }
- if(face==4){
- // 7 19 20 8
- // 22 2 14 12 24 17 5 10
- // 22 2 14 12 24 17 5 10
- swap(a[7],a[19]);swap(a[19],a[20]);swap(a[20],a[8]);
- 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]);
- 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]);
- }
- if(face==5){
- // 9 21 22 10
- // 6 3 4 1 2 7 8 5
- // 6 3 4 1 2 7 8 5
- swap(a[9],a[21]);swap(a[21],a[22]);swap(a[22],a[10]);
- 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]);
- 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]);
- }
- if(face==6){
- // 11 23 24 12
- // 13 16 15 18 17 20 19 14
- // 13 16 15 18 17 20 19 14
- swap(a[11],a[23]);swap(a[23],a[24]);swap(a[24],a[12]);
- 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]);
- 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]);
- }
- }
- unordered_map<ull,short>path;
- signed main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- string clr="*************************";
- for(int i=1;i<=24;i++){
- char x;
- cin>>x;
- if(x=='R')clr[i]=1;
- if(x=='G')clr[i]=2;
- if(x=='B')clr[i]=3;
- }
- int n=getnum(clr);
- if(solved(clr)){
- cout<<"Solved\n";
- return 0;
- }
- queue<pair<int,short>>q;
- q.push({n,0});
- path[n]=1;
- while(!q.empty()){
- int k=q.front().fi;
- int d=q.front().se;
- q.pop();
- string c=getstr(k);
- for(int i=1;i<=6;i++){
- for(int ii=1;ii<=2;ii++){
- string p=c;
- rotcube(p,i,ii);
- int kk=getnum(p);
- if(!path[kk]){
- if(solved(p)){
- vector<int>ans;
- ans.pb(2*i-1+ii-1);
- string a=getstr(k);
- int r=k;
- while(d--){
- ans.pb(path[r]);
- int face=(ans.back()+1)/2;
- rotcube(a,face, ans.back()%2+1);
- r=getnum(a);
- }
- //cout<<ans<<"\n";
- reverse(ans.begin(),ans.end());
- for(auto e:ans){
- if((e+1)/2==1)cout<<'F';
- if((e+1)/2==2)cout<<'L';
- if((e+1)/2==3)cout<<'B';
- if((e+1)/2==4)cout<<'R';
- if((e+1)/2==5)cout<<'U';
- if((e+1)/2==6)cout<<'D';
- if(e%2==1)cout<<"'";
- }
- cout<<"\n";
- return 0;
- }
- path[kk]=2*i-1+ii-1;
- q.push({kk,d+1});
- }
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement