Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma optimization_level 3
- #pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")
- #include<bits/stdc++.h>
- #define F first
- #define S second
- #define vec vector
- #define ms multiset
- #define pb push_back
- #define pll pair<ll,ll>
- #define pdd pair<ld, ld>
- #define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define pii pair<int, int>
- #define uid uniform_int_distribution
- #define FILE ifstream in("input.txt");ofstream out("output.txt");
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- using namespace std;
- typedef string str;
- typedef long long ll;
- typedef long double ld;
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- short dp[4000][4000][2][2];
- short opt[4000][4000][2][2];
- short n;
- pair<pair<short,short>, short> resif(int n){
- return {{n>>3, (n>>1)&((1<<2)-1)}, n&1};
- }
- short sifr(int a, int b, int c){
- return (((a<<2)+b)<<1)+c;
- }
- short gen(short a, short b, short xod, short eat, short isT){
- if(a+b==0) return eat;
- if(dp[a][b][xod][isT]!=-1) return dp[a][b][xod][isT]+eat;
- short o = 30000;
- if(!xod){
- if(a>0){
- o = gen(a-1,b,xod^1,eat,0);
- opt[a][b][xod][isT] = sifr(0,1,0);
- if(dp[a-1][b][xod^1][0]==-1) dp[a-1][b][xod^1][0] = o-eat;
- }
- if(b>0 && !isT){
- n = gen(a+1, b-1, xod^1, eat, 1);
- if(n<o){
- o = n;
- opt[a][b][xod][isT] = sifr(2,0,1);
- }
- if(dp[a+1][b-1][xod^1][1]==-1) dp[a+1][b-1][xod^1][1] = o-eat;
- }
- if(a==0 && isT){
- n = gen(a,b,xod^1,eat,0);
- if(n<o){
- o = n;
- opt[a][b][xod][isT] = sifr(1,1,0);
- }
- if(dp[a][b][xod^1][0]==-1) dp[a][b][xod^1][0] = o-eat;
- }
- }
- else{
- if(b>0){
- o = gen(a,b-1,xod^1,eat+1,0);
- opt[a][b][xod][isT] = sifr(1,0,0);
- if(dp[a][b-1][xod^1][0]==-1) dp[a][b-1][xod^1][0] = o-eat-1;
- }
- if(a>0 && !isT){
- n = gen(a-1, b+1, xod^1, eat, 1);
- if(n<o){
- o = n;
- opt[a][b][xod][isT] = sifr(0,2,1);
- }
- if(dp[a-1][b+1][xod^1][1]==-1) dp[a-1][b+1][xod^1][1] = o-eat;
- }
- if(b==0 && isT){
- n = gen(a,b,xod^1, eat,0);
- if(n<o){
- o = n;
- opt[a][b][xod][isT] = sifr(1,1,0);
- }
- if(dp[a][b][xod^1][0]==-1) dp[a][b][xod^1][0] = o-eat;
- }
- }
- return o;
- }
- int main() {
- fast; FILE;
- 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;
- short a,b,xod=0,isT=0; in>>a>>b;
- gen(a,b,0,0,0);
- vec<char> o;
- for(; a+b>0;){
- auto p = resif(opt[a][b][xod][isT]);
- char c = p.F.F==1 && p.F.S==1 ? 'W' : p.F.F!=1 && p.F.S!=1 ? 'T' : 'E';
- o.pb(c);
- a += p.F.F-1;
- b += p.F.S-1;
- xod ^= 1;
- isT = p.S;
- }
- out<<o.size()<<endl;
- for(char u : o) out<<u<<" ";
- }
Add Comment
Please, Sign In to add comment