fork(1) download 
  1. #pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
  4.  
  5. #define _CRT_SECURE_NO_WARNINGS
  6. # include <iostream>
  7. # include <cmath>
  8. # include <algorithm>
  9. # include <stdio.h>
  10. # include <cstdint>
  11. # include <cstring>
  12. # include <string>
  13. # include <cstdlib>
  14. # include <vector>
  15. # include <bitset>
  16. # include <map>
  17. # include <queue>
  18. # include <ctime>
  19. # include <stack>
  20. # include <set>
  21. # include <list>
  22. # include <random>
  23. # include <deque>
  24. # include <functional>
  25. # include <iomanip>
  26. # include <sstream>
  27. # include <fstream>
  28. # include <complex>
  29. # include <numeric>
  30. # include <immintrin.h>
  31. # include <cassert>
  32. # include <array>
  33. # include <tuple>
  34. # include <unordered_map>
  35. # include <unordered_set>
  36.  
  37. #ifdef LOCAL0000
  38. # include <opencv2/core/core.hpp>
  39. # include <opencv2/highgui/highgui.hpp>
  40. # include <opencv2/imgproc/imgproc.hpp>
  41. #endif
  42.  
  43. using namespace std;
  44.  
  45. #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
  46. #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
  47. #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
  48. #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
  49. #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
  50. #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
  51. #define macro_dispatcher___(macro, nargs) macro ## nargs
  52. #define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
  53. #define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  54. #define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  55. #define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  56. #define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
  57. #define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
  58. #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
  59. #define DA(a,n) cerr<<#a<<"=["; printarray(a,n); cerr<<"]\n"
  60. #define DAR(a,n,s) cerr<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cerr<<"]\n"
  61.  
  62. #ifdef _MSC_VER
  63. #define PREFETCH(ptr, rw, level) ((void)0)
  64. #else
  65. #define PREFETCH(ptr, rw, level) __builtin_prefetch(ptr, rw, level)
  66. #endif
  67.  
  68. #if defined _MSC_VER
  69. #define ASSUME(condition) ((void)0)
  70. #define __restrict
  71. #elif defined __clang__
  72. #define ASSUME(condition)       __builtin_assume(condition)
  73. #elif defined __GNUC__
  74. [[noreturn]] __attribute__((always_inline)) inline void undefinedBehaviour() {}
  75. #define ASSUME(condition)       ((condition) ? true : (undefinedBehaviour(), false))
  76. #endif
  77.  
  78. #ifdef LOCAL
  79. #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
  80. #else
  81. #define CURTIME()
  82. #endif
  83.  
  84. typedef long long ll;
  85. typedef long double ld;
  86. typedef unsigned int uint;
  87. typedef unsigned long long ull;
  88. typedef pair<int, int> pii;
  89. typedef pair<long long, long long> pll;
  90. typedef vector<int> vi;
  91. typedef vector<long long> vll;
  92. typedef int itn;
  93.  
  94. template<class T1, class T2, class T3>
  95. struct triple{ T1 a; T2 b; T3 c; triple() : a(T1()), b(T2()), c(T3()) {}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
  96. template<class T1, class T2, class T3>
  97. bool operator<(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a<t2.a;else if(t1.b!=t2.b)return t1.b<t2.b;else return t1.c<t2.c;}
  98. template<class T1, class T2, class T3>
  99. bool operator>(const triple<T1,T2,T3>&t1,const triple<T1,T2,T3>&t2){if(t1.a!=t2.a)return t1.a>t2.a;else if(t1.b!=t2.b)return t1.b>t2.b;else return t1.c>t2.c;}
  100. #define tri triple<int,int,int>
  101. #define trll triple<ll,ll,ll>
  102.  
  103. #define FI(n) for(int i=0;i<(n);++i)
  104. #define FJ(n) for(int j=0;j<(n);++j)
  105. #define FK(n) for(int k=0;k<(n);++k)
  106. #define FL(n) for(int l=0;l<(n);++l)
  107. #define FQ(n) for(int q=0;q<(n);++q)
  108. #define FOR(i,a,b) for(int i = (a), __e = (int) (b); i < __e; ++i)
  109. #define all(a) std::begin(a), std::end(a)
  110. #define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
  111.  
  112. #define sqr(x) ((x) * (x))
  113. #define sqrt(x) sqrt(1.0 * (x))
  114. #define pow(x, n) pow(1.0 * (x), n)
  115.  
  116. #define COMPARE(obj) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b)
  117. #define COMPARE_BY(obj, field) [&](const std::decay_t<decltype(obj)>& a, const std::decay_t<decltype(obj)>& b) { return a.field < b.field; }
  118.  
  119. #define checkbit(n, b) (((n) >> (b)) & 1)
  120. #define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  121. #define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  122. #define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  123. inline int countBits(uint v){v=v-((v>>1)&0x55555555);v=(v&0x33333333)+((v>>2)&0x33333333);return((v+(v>>4)&0xF0F0F0F)*0x1010101)>>24;}
  124. inline int countBits(ull v){uint t=v>>32;uint p=(v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
  125. inline int countBits(ll v){return countBits((ull)v); }
  126. inline int countBits(int v){return countBits((uint)v); }
  127. unsigned int reverseBits(uint x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
  128. template<class T> inline int sign(T x){ return x > 0 ? 1 : x < 0 ? -1 : 0; }
  129. inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
  130. constexpr ll power(ll x, int p) { return p == 0 ? 1 : (x * power(x, p - 1)); }
  131. template<class T>
  132. inline bool inRange(const T& val, const T& min, const T& max) { return min <= val && val <= max; }
  133. //template<class T1, class T2, class T3> T1 inline clamp(T1 x, const T2& a, const T3& b) { if (x < a) return a; else if (x > b) return b; else return x; }
  134. unsigned long long rdtsc() { unsigned long long ret = 0;
  135. #ifdef __clang__
  136.     return __builtin_readcyclecounter();
  137. #endif
  138. #ifndef _MSC_VER
  139.     asm volatile("rdtsc" : "=A" (ret) : :);
  140. #endif
  141.     return ret; }
  142. // Fast IO ********************************************************************************************************
  143. const int __BS = 4096;
  144. static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
  145. template<class T = int> T readInt() {
  146.     auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  147.     c(); while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir; c();
  148.     bool m = false; if (*__ir == '-') ++__ir, c(), m = true;
  149.     T r = 0; while (*__ir >= '0' && *__ir <= '9') r = r * 10 + *__ir - '0', ++__ir, c();
  150.     ++__ir; return m ? -r : r;
  151. }
  152. string readString() {
  153.     auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  154.     string r; c(); while (*__ir && isspace(*__ir)) ++__ir, c();
  155.     while (!isspace(*__ir)) r.push_back(*__ir), ++__ir, c();
  156.     ++__ir; return r;
  157. }
  158. char readChar() {
  159.     auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  160.     c(); while (*__ir && isspace(*__ir)) ++__ir, c(); return *__ir++;
  161. }
  162. static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
  163. template<class T>
  164. void writeInt(T x, char endc = '\n') {
  165.     if (x < 0) *__iw++ = '-', x = -x; if (x == 0) *__iw++ = '0';
  166.     char* s = __iw;
  167.     while (x) { T t = x / 10; char c = x - 10 * t + '0'; *__iw++ = c; x = t; }
  168.     char* f = __iw - 1; while (s < f) swap(*s, *f), ++s, --f;
  169.     if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
  170.     if (endc) { *__iw++ = endc; }
  171. }
  172. template<class T>
  173. void writeStr(const T& str) {
  174.     int i = 0; while (str[i]) { *__iw++ = str[i++]; if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw; }
  175. }
  176. struct __FL__ { ~__FL__() { if (__iw != __buw) cout.write(__buw, __iw - __buw); } };
  177. static __FL__ __flushVar__;
  178.  
  179. //STL output *****************************************************************************************************
  180. #define TT1 template<class T>
  181. #define TT1T2 template<class T1, class T2>
  182. #define TT1T2T3 template<class T1, class T2, class T3>
  183. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p);
  184. TT1 ostream& operator << (ostream& os, const vector<T>& v);
  185. TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v);
  186. TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v);
  187. TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v);
  188. TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>& v);
  189. TT1T2T3 ostream& operator << (ostream& os, const multimap<T1, T2, T3>& v);
  190. TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t);
  191. template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v);
  192. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
  193. TT1 ostream& operator << (ostream& os, const vector<T>& v){       bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  194. template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v) {     bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  195. TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){    bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  196. TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
  197. TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  198. TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
  199. TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
  200. TT1T2T3 ostream& operator << (ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
  201. TT1T2 void printarray(const T1& a, T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  202.  
  203. //STL input *****************************************************************************************************
  204. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t);
  205. TT1T2 inline istream& operator >> (istream& os, pair<T1, T2>& p) { return os >> p.first >> p.second; }
  206. TT1 inline istream& operator >> (istream& os, vector<T>& v) {
  207.     if (v.size()) for (T& t : v) os >> t; else {
  208.         string s; T obj; while (s.empty()) {getline(os, s); if (!os) return os;}
  209.         stringstream ss(s); while (ss >> obj) v.push_back(obj);
  210.     }
  211.     return os;
  212. }
  213. TT1T2T3 inline istream& operator >> (istream& os, triple<T1, T2, T3>& t) { return os >> t.a >> t.b >> t.c; }
  214.  
  215. //Pair magic *****************************************************************************************************
  216. #define PT1T2 pair<T1, T2>
  217. TT1T2 inline PT1T2 operator+(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first + p2.first, p1.second + p2.second); }
  218. TT1T2 inline PT1T2& operator+=(PT1T2 &p1 , const PT1T2 &p2) { p1.first += p2.first, p1.second += p2.second; return p1; }
  219. TT1T2 inline PT1T2 operator-(const PT1T2 &p1 , const PT1T2 &p2) { return PT1T2(p1.first - p2.first, p1.second - p2.second); }
  220. TT1T2 inline PT1T2& operator-=(PT1T2 &p1 , const PT1T2 &p2) { p1.first -= p2.first, p1.second -= p2.second; return p1; }
  221.  
  222. #undef TT1
  223. #undef TT1T2
  224. #undef TT1T2T3
  225.  
  226. #define FREIN(FILE) freopen(FILE, "rt", stdin)
  227. #define FREOUT(FILE) freopen(FILE, "wt", stdout)
  228. #ifdef LOCAL
  229. #define BEGIN_PROFILE(idx, name) int profileIdx = idx; profileName[profileIdx] = name; totalTime[profileIdx] -= rdtsc() / 1e3;
  230. #define END_PROFILE totalTime[profileIdx] += rdtsc() / 1e3; totalCount[profileIdx]++;
  231. #else
  232. #define BEGIN_PROFILE(idx, name)
  233. #define END_PROFILE
  234. #endif
  235.  
  236. const int USUAL_MOD = 1000000007;
  237. template<class T> inline void normmod(T &x, T m = USUAL_MOD) { x %= m; if (x < 0) x += m; }
  238. template<class T1, class T2> inline T2 summodfast(T1 x, T1 y, T2 m = USUAL_MOD) { T2 res = x + y; if (res >= m) res -= m; return res; }
  239. template<class T1, class T2, class T3 = int> inline void addmodfast(T1 &x, T2 y, T3 m = USUAL_MOD) { x += y; if (x >= m) x -= m; }
  240. template<class T1, class T2, class T3 = int> inline void submodfast(T1 &x, T2 y, T3 m = USUAL_MOD) { x -= y; if (x < 0) x += m; }
  241. inline ll mulmod(ll x, ll n, ll m){ x %= m; n %= m; ll r = x * n - ll(ld(x)*ld(n) / ld(m)) * m; while (r < 0) r += m; while (r >= m) r -= m; return r; }
  242. inline ll powmod(ll x, ll n, ll m){ ll r = 1; normmod(x, m); while (n){ if (n & 1) r *= x; x *= x; r %= m; x %= m; n /= 2; }return r; }
  243. inline ll powmulmod(ll x, ll n, ll m) { ll res = 1; normmod(x, m); while (n){ if (n & 1)res = mulmod(res, x, m); x = mulmod(x, x, m); n /= 2; } return res; }
  244. template<class T> inline T gcd(T a, T b) { while (b) { T t = a % b; a = b; b = t; } return a; }
  245. template<class T>
  246. T fast_gcd(T u, T v) {
  247.     int shl = 0; while ( u && v && u != v) { T eu = u & 1; u >>= eu ^ 1; T ev = v & 1; v >>= ev ^ 1;
  248.         shl += (~(eu | ev) & 1); T d = u & v & 1 ? (u + v) >> 1 : 0; T dif = (u - v) >> (sizeof(T) * 8 - 1); u -= d & ~dif; v -= d & dif;
  249.     } return std::max(u, v) << shl;
  250. }
  251.  
  252. inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }
  253. template<class T> inline T gcd(T a, T b, T c){ return gcd(gcd(a, b), c); }
  254. ll gcdex(ll a, ll b, ll& x, ll& y) {
  255.     if (!a) { x = 0; y = 1; return b; }
  256.     ll y1; ll d = gcdex(b % a, a, y, y1); x = y1 - (b / a) * y;
  257.     return d;
  258. }
  259. template<class T> bool isPrime(T x) { if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3;
  260.     for (T i = 5; i * i <= x; i += 6) if (x % i == 0 || x % (i + 2) == 0) return 0; return 1; }
  261. bool millerRabin(long long n) {
  262.     if (n <= 1000) return isPrime(n);
  263.     long long s = n - 1; int t = 0; while (s % 2 == 0) s /= 2, ++t;
  264.     for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if (!(a %= n)) return true;
  265.         long long f = powmulmod(a, s, n); if (f == 1 || f == n - 1) continue;
  266.         for (int i = 1; i < t; ++i) if ((f = mulmod(f, f, n)) == n - 1) goto nextp;
  267.         return false; nextp:;
  268.     } return true;
  269. }
  270.  
  271. // Useful constants
  272.  
  273. //int some_primes[7] = {24443, 100271, 1000003, 1000333, 5000321, 98765431,
  274. #define T9          1000000000
  275. #define T18         1000000000000000000LL
  276. #define INF         1011111111
  277. #define LLINF       1000111000111000111LL
  278. #define mod         1000000007
  279. #define fftmod      998244353
  280. #define EPS         (double)1e-10
  281. #define PI          3.14159265358979323846264
  282. #define link        asaxlajrewqwe
  283. #define rank        wahayawehasdakw
  284. //*************************************************************************************
  285.  
  286.  
  287. int32_t solve();
  288. int32_t main(int argc, char** argv) {
  289.     ios_base::sync_with_stdio(0);cin.tie(0);
  290. #ifdef LOCAL
  291.     if (argc == 1 || argv[1] == string("test")) {
  292.         FREIN("examples/001");
  293.     } else {
  294.         FREIN(argv[1]);
  295.     }
  296.     FREOUT("out.txt");
  297. #endif
  298.     return solve();
  299. }
  300. string world;
  301. string q;
  302. constexpr int MAXQ = 10010;
  303. constexpr int TEN = 10;
  304.  
  305. template <typename T, size_t N> struct alignas(16) aligned_array : public std::array<T, N> {};
  306. using ArrTen = array<int, TEN>;
  307. void updString(string& s) { for (char& c : s) c -= 'A'; }
  308. mt19937_64 gen;
  309. int rnd(int n) {
  310.     return uniform_int_distribution<>(0, n - 1)(gen);
  311. }
  312. ArrTen nex[50001];
  313. struct Hist {
  314.     Hist *parent;
  315.     pii move;
  316. };
  317. Hist allHist[1 << 21];
  318. Hist *lastHist = allHist;
  319. vector<Hist*> histPool;
  320. Hist *getNewHist() {
  321.     if (histPool.empty()) {
  322.         return lastHist++;
  323.     } else {
  324.         auto res = histPool.back();
  325.         histPool.pop_back();
  326.         return res;
  327.     }
  328. }
  329. /***** PARAMS *****/
  330. int NOT_LAST_BONUS = 8;
  331. constexpr int MAX_STATES_CNT = 60;
  332. constexpr int DEPTH1_TRIES = 6;
  333. constexpr int DEPTH0_TRIES = 2;
  334. constexpr int GREEDY_STEPS = 24;
  335. /***** PARAMS *****/
  336. bool used[50000];
  337. struct State {
  338.     ArrTen whereIsUnit = {};
  339.     ArrTen colorsInPocket = {};
  340.     int score = 0;
  341.     Hist* hist = nullptr;
  342.     int calcScore() {
  343.         int score = 0;
  344.         auto tmp = whereIsUnit;
  345.         sort(tmp.begin(), tmp.end(), std::greater<int>());
  346.         for (int i = 0; i < TEN; ++i) {
  347.             score += (i + 4) * tmp[i];
  348.         }
  349.         score += tmp[TEN - 1] * 8;
  350.         return score;
  351.     }
  352.     inline bool anyoneAtPos(int pos) const {
  353.         for (int x : whereIsUnit) {
  354.             if (x == pos) return true;
  355.         }
  356.         return false;
  357.     }
  358.     int getLastUnit() const {
  359.         return int(min_element(all(whereIsUnit)) - begin(whereIsUnit));
  360.     }
  361.     int getNextSameColor_Used(int pos, int color) const {
  362.         do {
  363.             pos = nex[pos][color];
  364.         } while (used[pos]);
  365.         return pos;
  366.     }
  367.     int getNextSameColor(int pos, int color) const {
  368.         do {
  369.             pos = nex[pos][color];
  370.         } while (anyoneAtPos(pos));
  371.         return pos;
  372.     }
  373.     inline void addColor(int color) {
  374.         colorsInPocket[color]++;
  375.     }
  376.     inline void delColor(int color) {
  377.         colorsInPocket[color]--;
  378.     }
  379.     void makeTheMove(int idx, int color) {
  380.         whereIsUnit[idx] = getNextSameColor(whereIsUnit[idx], color);
  381.         delColor(color);
  382.     }
  383.     void makeTheMove(int idx, int color, int pos) {
  384.         whereIsUnit[idx] = pos;
  385.         delColor(color);
  386.     }
  387.     void mutateGreedy(int cur, int stepsCnt) {
  388.         for (int x : whereIsUnit) {
  389.             used[x] = true;
  390.         }
  391.         while (stepsCnt-- > 0 && cur < MAXQ) {
  392.             addColor(q[cur++]);
  393.             int idx = getLastUnit();
  394.             int pos = whereIsUnit[idx];
  395.             used[pos] = false;
  396.             int maxNextPos = -1;
  397.             int what = -1;
  398.             for (int i = 0; i < TEN; ++i) {
  399.                 if (!colorsInPocket[i]) continue;
  400.                 int nextPos = getNextSameColor_Used(pos, i);
  401.                 if (nextPos > maxNextPos) {
  402.                     maxNextPos = nextPos;
  403.                     what = i;
  404.                 }
  405.             }
  406.             used[maxNextPos] = true;
  407.             makeTheMove(idx, what, maxNextPos);
  408.         }
  409.         for (int x : whereIsUnit) {
  410.             used[x] = false;
  411.         }
  412.     }
  413.     template<int depth>
  414.     int generateNewStates(int maxCnt, State* res, int cur) {
  415.         addColor(q[cur]);
  416.         tri whoWhatAndWhere[depth == 0 ? 10 : 100];
  417.         int sz = 0;
  418.         int idx = getLastUnit();
  419.         for (int who = (depth ? 0 : idx); who < (depth ? TEN : idx + 1); ++who) {
  420.             for (int what = 0; what < TEN; ++what) {
  421.                 if (!colorsInPocket[what]) continue;
  422.                 int where = getNextSameColor(whereIsUnit[who], what) - whereIsUnit[who];
  423.                 if (idx != who) {
  424.                     where -= NOT_LAST_BONUS;
  425.                 }
  426.                 whoWhatAndWhere[sz++] = {who, what, where};
  427.             }
  428.         }
  429.         sort(whoWhatAndWhere, whoWhatAndWhere + sz , [](tri a, tri b){
  430.             return a.c > b.c;
  431.         });
  432.         int resultMoves = 0;
  433.         maxCnt = min(maxCnt, sz);
  434.         for (auto [who, what, _] : whoWhatAndWhere) {
  435.             if (maxCnt-- == 0) break;
  436.             int oldPos = whereIsUnit[who];
  437.             int where = getNextSameColor(oldPos, what);
  438.             makeTheMove(who, what, where);
  439.             if (depth == 0 || cur + 1 == MAXQ) {
  440.                 auto greedy = *this;
  441.                 greedy.mutateGreedy(cur + 1, GREEDY_STEPS);
  442.                 score = max(score, greedy.calcScore());
  443.             } else {
  444.                 score = 0;
  445.                 generateNewStates<0>(DEPTH0_TRIES, nullptr, cur + 1);
  446.             }
  447.             if (res != nullptr) {
  448.                 auto prevHist = hist;
  449.                 hist = getNewHist();
  450.                 hist->move = {who, what};
  451.                 hist->parent = prevHist;
  452.                 *res++ = *this;
  453.                 hist = prevHist;
  454.             }
  455.             whereIsUnit[who] = oldPos;
  456.             colorsInPocket[what]++;
  457.             ++resultMoves;
  458.         }
  459.         delColor(q[cur]);
  460.         return resultMoves;
  461.     }
  462. };
  463. std::ostream& operator<<(std::ostream& os, const State& s) {
  464.     return os << s.colorsInPocket << ' ' << s.whereIsUnit;
  465. }
  466. bool operator < (const State& a, const State& b) {
  467.     return (a.score > b.score) || (a.score == b.score && a.colorsInPocket < b.colorsInPocket);
  468. }
  469. bool operator == (const State& a, const State& b) {
  470.     return a.score == b.score && a.colorsInPocket == b.colorsInPocket;
  471. }
  472. int solve() {
  473.     //    ifstream fin("examples/001");
  474.     int n, s, c, h, U;
  475.     cin >> n >> s >> c >> h >> U;
  476.     cin >> world;
  477.     cin >> q;
  478.     updString(world);
  479.     updString(q);
  480.     const int MAXPOS = 50000;
  481.     for (int i = 0; i < TEN; ++i) nex[MAXPOS][i] = MAXPOS;
  482.     for (int i = MAXPOS - 1; i >= 0; --i) {
  483.         for (int j = 0; j < TEN; ++j) {
  484.             nex[i][j] = nex[i + 1][j];
  485.         }
  486.         nex[i][world[i + 1]] = i + 1;
  487.     }
  488.     static int indices[MAX_STATES_CNT * TEN];
  489.     static State __states[2][MAX_STATES_CNT * TEN];
  490.     auto states = __states[0];
  491.     auto newStates = __states[1];
  492.     int statesCnt = 1;
  493.     for (int i = 0; i < TEN - 1; ++i) {
  494.         states[0].addColor(q[i]);
  495.     }
  496.     for (int i = 0; i < TEN; ++i) {
  497.         states[0].whereIsUnit[i] = i;
  498.     }
  499.     for (int i = TEN - 1; i + 1 < (int)q.size(); ++i) {
  500.         if (i == 9000) NOT_LAST_BONUS = 24;
  501.         if (i == 9500) NOT_LAST_BONUS = 64;
  502.         if (i == 9900) NOT_LAST_BONUS = 256;
  503.         for (int i = 0; i < statesCnt; ++i) {
  504.             indices[i] = i;
  505.         }
  506.         auto cmp = [&](int x, int y) { return states[x] < states[y]; };
  507.         shuffle(indices, indices + statesCnt, gen);
  508.         sort(indices, indices + statesCnt, cmp);
  509.         int oldStatesCnt = statesCnt;
  510.         statesCnt = 1;
  511.         for (int j = 1; j < oldStatesCnt; ++j) {
  512.             int x = indices[j];
  513.             int y = indices[statesCnt - 1];
  514.             if (statesCnt == MAX_STATES_CNT || states[x] == states[y]) {
  515.                 histPool.push_back(states[x].hist);
  516.             } else {
  517.                 indices[statesCnt++] = x;
  518.             }
  519.         }
  520.         int newStatesCnt = 0;
  521.         for (int j = 0; j < statesCnt; ++j) {
  522.             auto& state = states[indices[j]];
  523.             state.score = 0;
  524.             newStatesCnt += state.generateNewStates<1>(DEPTH1_TRIES, newStates + newStatesCnt, i);
  525.         }
  526.         statesCnt = newStatesCnt;
  527.         swap(states, newStates);
  528.     }
  529.     sort(states, states + statesCnt);
  530.     auto bestScore = states[0].whereIsUnit[states[0].getLastUnit()];
  531.     vector<pii> ans;
  532.     auto hist = states[0].hist;
  533.     while (hist != nullptr) {
  534.         ans.push_back(hist->move);
  535.         hist = hist->parent;
  536.     }
  537.     reverse(all(ans));
  538.     for (auto p : ans) {
  539.         cout << p.first << ' ' << char(p.second + 'A') << endl;
  540.     }
  541.     DBN(bestScore);
  542.     CURTIME();
  543.     FREOUT("score.txt");
  544.     cout << bestScore << endl;
  545.     //    DBN(bestScore);
  546.     return 0;
  547. }
  548.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In member function ‘int State::generateNewStates(int, State*, int)’:
prog.cpp:434:19: error: expected unqualified-id before ‘[’ token
         for (auto [who, what, _] : whoWhatAndWhere) {
                   ^
prog.cpp:434:19: error: expected ‘;’ before ‘[’ token
prog.cpp:434:20: error: ‘who’ was not declared in this scope
         for (auto [who, what, _] : whoWhatAndWhere) {
                    ^~~
prog.cpp:434:25: error: ‘what’ was not declared in this scope
         for (auto [who, what, _] : whoWhatAndWhere) {
                         ^~~~
prog.cpp:434:31: error: ‘_’ was not declared in this scope
         for (auto [who, what, _] : whoWhatAndWhere) {
                               ^
prog.cpp: In lambda function:
prog.cpp:434:34: error: expected ‘{’ before ‘:’ token
         for (auto [who, what, _] : whoWhatAndWhere) {
                                  ^
prog.cpp: In member function ‘int State::generateNewStates(int, State*, int)’:
prog.cpp:434:34: error: expected ‘;’ before ‘:’ token
prog.cpp:434:34: error: expected primary-expression before ‘:’ token
prog.cpp:434:34: error: expected ‘)’ before ‘:’ token
prog.cpp:434:34: error: expected primary-expression before ‘:’ token
stdout 
Standard output is empty
https://ideone.com/UXF5B4
language:
C++14 (gcc 8.3)
created:
6 years 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!