wery00

Untitled

Apr 27th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.19 KB | None | 0 0
  1. #pragma optimization_level 3
  2. #pragma GCC optimize("Ofast,no-stack-protector")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("fast-math")
  5. #include<bits/stdc++.h>
  6. #define F first
  7. #define S second
  8. #define vec vector
  9. #define ms multiset
  10. #define pb push_back
  11. #define pll pair<ll,ll>
  12. #define pdd pair<ld, ld>
  13. #define pq priority_queue
  14. #define umap unordered_map
  15. #define uset unordered_set
  16. #define pii pair<int, int>
  17. #define uid uniform_int_distribution
  18. #define FILE ifstream in("input.txt");ofstream out("output.txt");
  19. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  20. using namespace std;
  21. typedef string str;
  22. typedef long long ll;
  23. typedef long double ld;
  24. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26. short dp[4000][4000][2][2];
  27. short opt[4000][4000][2][2];
  28.  
  29. short n;
  30.  
  31. pair<pair<short,short>, short> resif(int n){
  32.     return {{n>>3, (n>>1)&((1<<2)-1)}, n&1};
  33. }
  34.  
  35. short sifr(int a, int b, int c){
  36.     return (((a<<2)+b)<<1)+c;
  37. }
  38.  
  39. short gen(short a, short b, short xod, short eat, short isT){
  40.     if(a+b==0) return eat;
  41.     if(dp[a][b][xod][isT]!=-1) return dp[a][b][xod][isT]+eat;
  42.     short o = 30000;
  43.     if(!xod){
  44.         if(a>0){
  45.             o = gen(a-1,b,xod^1,eat,0);
  46.             opt[a][b][xod][isT] = sifr(0,1,0);
  47.             if(dp[a-1][b][xod^1][0]==-1) dp[a-1][b][xod^1][0] = o-eat;
  48.         }
  49.         if(b>0 && !isT){
  50.             n = gen(a+1, b-1, xod^1, eat, 1);
  51.             if(n<o){
  52.                 o = n;
  53.                 opt[a][b][xod][isT] = sifr(2,0,1);
  54.             }
  55.             if(dp[a+1][b-1][xod^1][1]==-1) dp[a+1][b-1][xod^1][1] = o-eat;
  56.         }
  57.         if(a==0 && isT){
  58.             n = gen(a,b,xod^1,eat,0);
  59.             if(n<o){
  60.                 o = n;
  61.                 opt[a][b][xod][isT] = sifr(1,1,0);
  62.             }
  63.             if(dp[a][b][xod^1][0]==-1) dp[a][b][xod^1][0] = o-eat;
  64.         }
  65.     }
  66.     else{
  67.         if(b>0){
  68.             o = gen(a,b-1,xod^1,eat+1,0);
  69.             opt[a][b][xod][isT] = sifr(1,0,0);
  70.             if(dp[a][b-1][xod^1][0]==-1) dp[a][b-1][xod^1][0] = o-eat-1;
  71.         }
  72.         if(a>0 && !isT){
  73.             n = gen(a-1, b+1, xod^1, eat, 1);
  74.             if(n<o){
  75.                 o = n;
  76.                 opt[a][b][xod][isT] = sifr(0,2,1);
  77.             }
  78.             if(dp[a-1][b+1][xod^1][1]==-1) dp[a-1][b+1][xod^1][1] = o-eat;
  79.         }
  80.         if(b==0 && isT){
  81.             n = gen(a,b,xod^1, eat,0);
  82.             if(n<o){
  83.                 o = n;
  84.                 opt[a][b][xod][isT] = sifr(1,1,0);
  85.             }
  86.             if(dp[a][b][xod^1][0]==-1) dp[a][b][xod^1][0] = o-eat;
  87.         }
  88.     }
  89.     return o;
  90. }
  91.  
  92. int main() {
  93.     fast; FILE;
  94.     for(int q=0; q<4000; q++) for(int w=0; w<4000; w++) for(int e=0; e<2; e++) for(int r=0; r<2; r++) dp[q][w][e][r] = -1;
  95.     short a,b,xod=0,isT=0; in>>a>>b;
  96.     gen(a,b,0,0,0);
  97.     vec<char> o;
  98.     for(; a+b>0;){
  99.         auto p = resif(opt[a][b][xod][isT]);
  100.         char c = p.F.F==1 && p.F.S==1 ? 'W' : p.F.F!=1 && p.F.S!=1 ? 'T' : 'E';
  101.         o.pb(c);
  102.         a += p.F.F-1;
  103.         b += p.F.S-1;
  104.         xod ^= 1;
  105.         isT = p.S;
  106.     }
  107.     out<<o.size()<<endl;
  108.     for(char u : o) out<<u<<" ";
  109. }
Add Comment
Please, Sign In to add comment