API tools faq
paste
Guest User

ilyakor's solution for Game of Amazons from Hackerearth

a guest
Jan 19th, 2016
239
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.91 KB | None | 0 0
raw download clone embed print report
  1. #include <string>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <sstream>
  8. #include <cmath>
  9. #include <cassert>
  10. #include <queue>
  11. #include <bitset>
  12. #include <map>
  13. #include <set>
  14.  
  15. #define pb push_back
  16. #define mp make_pair
  17. #define sz(v) ((int)(v).size())
  18. #define all(v) (v).begin(),(v).end()
  19.  
  20. using namespace std;
  21.  
  22. typedef long long int64;
  23. typedef pair<int, int> ii;
  24. typedef vector<int> vi;
  25.  
  26. const int N = 10;
  27. const int N2 = N * N;
  28.  
  29. struct Move {
  30.   int x0, y0;
  31.   int x1, y1;
  32.   int x2, y2;
  33.  
  34.   Move() : x0(-1) {}
  35.   Move(int x0, int y0, int x1, int y1, int x2, int y2)
  36.       : x0(x0), y0(y0), x1(x1), y1(y1), x2(x2), y2(y2) {}
  37.   Move(int cell0, int cell1, int cell2)
  38.       : x0(cell0 / N), y0(cell0 % N),
  39.         x1(cell1 / N), y1(cell1 % N),
  40.         x2(cell2 / N), y2(cell2 % N) {}
  41.  
  42.   bool operator<(const Move& other) const {
  43.     return false;
  44.   }
  45.  
  46.   bool IsValid() const {
  47.     return x0 != -1;
  48.   }
  49.  
  50.   int Cell0() const {
  51.     return x0 * N + y0;
  52.   }
  53.  
  54.   int Cell1() const {
  55.     return x1 * N + y1;
  56.   }
  57.  
  58.   int Cell2() const {
  59.     return x2 * N + y2;
  60.   }
  61. };
  62.  
  63. struct ScoringConfig {
  64.   int own;
  65.   int both;
  66.  
  67.   ScoringConfig() : own(16), both(1) {}
  68.   ScoringConfig(int own, int both)
  69.       : own(own), both(both) {}
  70. };
  71.  
  72. struct Board {
  73.   // TODO: reverse index for queens.
  74.   char field[N2];
  75.   int player;
  76.   int move_index;
  77.  
  78.   bool has_score;
  79.   int score;
  80.  
  81.   Board() {
  82.     memset(field, 0, sizeof(field));
  83.     player = 0;
  84.     move_index = 0;
  85.     has_score = false;
  86.     score = 0;
  87.     field[0 * N + 3] = -1;
  88.     field[0 * N + 6] = -1;
  89.     field[3 * N + 0] = -1;
  90.     field[3 * N + 9] = -1;
  91.     field[6 * N + 0] = 1;
  92.     field[6 * N + 9] = 1;
  93.     field[9 * N + 3] = 1;
  94.     field[9 * N + 6] = 1;
  95.   }
  96.  
  97.   Board(const Board& other) {
  98.     memcpy(field, other.field, sizeof(field));
  99.     player = other.player;
  100.     move_index = other.move_index;
  101.     has_score = other.has_score;
  102.     score = other.score;
  103.   }
  104.  
  105.   vector<Move> GetAllMoves() {
  106.     vector<Move> res;
  107.     int p = player == 0 ? 1 : -1;
  108.     for (int x = 0; x < N; ++x)
  109.       for (int y = 0; y < N; ++y) {
  110.         if (field[x * N + y] != p)
  111.           continue;
  112.         vector<int> cells = QueenMoves(x, y);
  113.         for (int i = 0; i < sz(cells); ++i) {
  114.           int x1 = cells[i] / N, y1 = cells[i] % N;
  115.           swap(field[x * N + y], field[cells[i]]);
  116.           vector<int> cells1 = QueenMoves(x1, y1);
  117.           swap(field[x * N + y], field[cells[i]]);
  118.           for (int j = 0; j < sz(cells1); ++j) {
  119.             res.pb(Move(x, y, x1, y1, cells1[j] / N, cells1[j] % N));
  120.           }
  121.         }
  122.       }
  123.     return res;
  124.   }
  125.  
  126.   Move GetRandomMove() {
  127.     vi queens;
  128.     int p = player == 0 ? 1 : -1;
  129.     for (int x = 0; x < N; ++x)
  130.       for (int y = 0; y < N; ++y) {
  131.         if (field[x * N + y] != p) continue;
  132.         queens.pb(x * N + y);
  133.       }
  134.     random_shuffle(all(queens));
  135.     vector<vector<int> > queen_moves;
  136.     int total_moves = 0;
  137.     for (int i = 0; i < sz(queens); ++i) {
  138.       int x = queens[i] / N, y = queens[i] % N;
  139.       vector<int> cells = QueenMoves(x, y);
  140.       queen_moves.pb(cells);
  141.       total_moves += sz(cells);
  142.     }
  143.     if (total_moves == 0)
  144.       return Move();
  145.     int r = rand() % total_moves;
  146.     for (int i = 0; i < sz(queens); ++i) {
  147.       r -= sz(queen_moves[i]);
  148.       if (r >= 0) continue;
  149.       int x = queens[i] / N, y = queens[i] % N;
  150.       vector<int> cells = queen_moves[i];
  151.       random_shuffle(all(cells));
  152.       for (int j = 0; j < sz(cells); ++j) {
  153.         int x1 = cells[j] / N, y1 = cells[j] % N;
  154.         swap(field[x * N + y], field[cells[j]]);
  155.         vector<int> cells1 = QueenMoves(x1, y1);
  156.         swap(field[x * N + y], field[cells[j]]);
  157.         random_shuffle(all(cells1));
  158.         assert(sz(cells1) > 0);
  159.         return Move(x, y, x1, y1, cells1[0] / N, cells1[0] % N);
  160.       }
  161.     }
  162.     return Move();
  163.   }
  164.  
  165.   void ApplyMove(const Move& move) {
  166.     int cell0 = move.Cell0();
  167.     int cell1 = move.Cell1();
  168.     int cell2 = move.Cell2();
  169.     int p = player == 0 ? 1 : -1;
  170.     assert(field[cell0] == p);
  171.     assert(field[cell1] == 0);
  172.     assert(field[cell2] == 0 || cell2 == cell0);
  173.     field[cell0] = 0;
  174.     field[cell1] = p;
  175.     field[cell2] = p * 2;
  176.  
  177.     player = 1 - player;
  178.     ++move_index;
  179.     has_score = false;
  180.     score = 0;
  181.   }
  182.  
  183.   void UndoMove(const Move& move) {
  184.     int cell0 = move.Cell0();
  185.     int cell1 = move.Cell1();
  186.     int cell2 = move.Cell2();
  187.     int p = player == 0 ? -1 : 1;
  188.     assert(field[cell0] == 0 || cell2 == cell0);
  189.     assert(field[cell1] == p);
  190.     assert(field[cell2] == 2 * p);
  191.     field[cell1] = 0;
  192.     field[cell2] = 0;
  193.     field[cell0] = p;
  194.  
  195.     player = 1 - player;
  196.     --move_index;
  197.     has_score = false;
  198.     score = 0;
  199.   }
  200.  
  201.   vector<int> QueenMoves(int x, int y) const {
  202.     vector<int> res;
  203.     for (int dx = -1; dx <= 1; ++dx)
  204.       for (int dy = -1; dy <= 1; ++dy) {
  205.         if (dx == 0 && dy == 0) continue;
  206.         int cx = x + dx, cy = y + dy;
  207.         while (cx >= 0 && cx < N && cy >= 0 && cy < N &&
  208.                field[cx * N + cy] == 0) {
  209.           res.pb(cx * N + cy);
  210.           cx += dx;
  211.           cy += dy;
  212.         }
  213.       }
  214.     return res;
  215.   }
  216.  
  217.   int Score(const ScoringConfig& config) {
  218.     if (has_score)
  219.       return score;
  220.  
  221.     char u[N2];
  222.     memset(u, 0, sizeof(u));
  223.     char q[N2 + 4];
  224.     bitset<N2> borders;
  225.     int head = 0, tail = 0;
  226.     int p = player == 0 ? 1 : -1;
  227.     for (int s = -1; s <= 1; s += 2)
  228.       for (int x = 0; x < N; ++x)
  229.         for (int y = 0; y < N; ++y) {
  230.           if (field[x * N + y] != -s * p) continue;
  231.           q[tail++] = x * N + y;
  232.           u[x * N + y] = field[x * N + y];
  233.         }
  234.     score = 0;
  235.     while (tail > head) {
  236.       int cell = q[head++];
  237.       int nd = u[cell];
  238.       if (nd < 0) --nd;
  239.       else ++nd;
  240.       int x = cell / N, y = cell % N;
  241.       vector<int> cells = QueenMoves(x, y);
  242.       for (int i = 0; i < sz(cells); ++i) {
  243.         int c = cells[i];
  244.         if (u[c]) {
  245.           if (u[c] * p > 0 && u[c] == -nd && !borders[c]) {
  246.             borders[c] = true;
  247.             score += (config.both - config.own) * p;
  248.           }
  249.           continue;
  250.         }
  251.         u[c] = nd;
  252.         if (u[c] < 0){
  253.           score -= config.own;
  254.         } else {
  255.           score += config.own;
  256.         }
  257.         q[tail++] = c;
  258.       }
  259.     }
  260.  
  261.     has_score = true;
  262.     return score;
  263.   }
  264.  
  265.   string ToString() {
  266.     ostringstream res;
  267.     res << "Player: " << player << " (move: " << move_index << ", score: "
  268.         << Score(ScoringConfig()) << ")\n";
  269.     for (int i = 0; i < N; ++i) {
  270.       for (int j = 0; j < N; ++j) {
  271.         char c;
  272.         if (field[i * N + j] == 0)
  273.           c = '.';
  274.         else if (field[i * N + j] == 1)
  275.           c = 'x';
  276.         else if (field[i * N + j] == -1)
  277.           c = 'o';
  278.         else
  279.           c = '#';
  280.         res << c;
  281.       }
  282.       res << "\n";
  283.     }
  284.     res << "\n";
  285.  
  286.     return res.str();
  287.   }
  288. };
  289.  
  290. class Strategy {
  291.  public:
  292.   virtual Move GetMove(Board board) = 0;
  293. };
  294.  
  295. class RandomStrategy : public Strategy {
  296.  public:
  297.   virtual Move GetMove(Board board) {
  298.     return board.GetRandomMove();
  299.   }
  300. };
  301.  
  302. class GreedyDepth1 : public Strategy {
  303.  public:
  304.   GreedyDepth1() {}
  305.  
  306.   GreedyDepth1(ScoringConfig scoring_config)
  307.       : scoring_config(scoring_config) {}
  308.  
  309.   virtual Move GetMove(Board board) {
  310.     vector<Move> moves = board.GetAllMoves();
  311.     Move res;
  312.     int res_score = -1000 * 1000;
  313.     for (int i = 0; i < sz(moves); ++i) {
  314.       Move move = moves[i];
  315.       board.ApplyMove(move);
  316.       int cur = board.Score(scoring_config);
  317.       board.UndoMove(move);
  318.       if (board.player == 1)
  319.         cur *= -1;
  320.       if (cur > res_score) {
  321.         res_score = cur;
  322.         res = move;
  323.       }
  324.     }
  325.     return res;
  326.   }
  327.  
  328.  private:
  329.   ScoringConfig scoring_config;
  330. };
  331.  
  332. const int inf = 1000 * 1000 * 1000;
  333.  
  334. class AlphaBeta : public Strategy {
  335.  public:
  336.   AlphaBeta(ScoringConfig scoring_config, int max_depth, double tl, int max_moves)
  337.       : max_depth(max_depth), tl(tl), max_moves(max_moves) {}
  338.  
  339.   virtual Move GetMove(Board board) {
  340.     start_time = clock();
  341.  
  342.     Move res = Move();
  343.     for (int depth = 1; depth <= max_depth; ++depth) {
  344.       best_move = Move();
  345.       Search(board, depth, -inf, inf, true /* is_root */);
  346.       if (TLExceeded())
  347.         break;
  348.       res = best_move;
  349.     }
  350.     return res;
  351.   }
  352.  
  353.  private:
  354.   bool TLExceeded() {
  355.     return clock() - start_time > tl * CLOCKS_PER_SEC;
  356.   }
  357.  
  358.   int Search(Board& board, int depth, int alpha, int beta, bool is_root=false) {
  359.     if (depth == 0)
  360.       return board.Score(scoring_config);
  361.     if (TLExceeded())
  362.       return board.player == 0 ? -inf : inf;
  363.     vector<Move> moves;
  364.     vector<Move> raw_moves = board.GetAllMoves();
  365.     vector<pair<double, Move> > scored_moves;
  366.     for (int i = 0; i < sz(raw_moves); ++i) {
  367.       Move move = raw_moves[i];
  368.       board.ApplyMove(move);
  369.       double score = board.Score(scoring_config);
  370.       board.UndoMove(move);
  371.       if (board.player == 0)
  372.         score = -score;
  373.       scored_moves.pb(mp(score, move));
  374.     }
  375.     sort(all(scored_moves));
  376.     for (int i = 0; i < sz(scored_moves) && i < max_moves; ++i)
  377.       moves.pb(scored_moves[i].second);
  378.  
  379.     if (sz(moves) == 0)
  380.       return board.Score(scoring_config);
  381.     if (depth == 1 && !is_root) {
  382.       return scored_moves[0].first * (board.player == 0 ? -1 : 1);
  383.     }
  384.  
  385.     if (board.player == 0) {
  386.       int res = -inf;
  387.       for (int i = 0; i < sz(moves); ++i) {
  388.         board.ApplyMove(moves[i]);
  389.         int cur = Search(board, depth - 1, alpha, beta);
  390.         board.UndoMove(moves[i]);
  391.         if (res < cur) {
  392.           res = cur;
  393.           if (is_root)
  394.             best_move = moves[i];
  395.         }
  396.         if (res > alpha)
  397.           alpha = res;
  398.         if (beta <= alpha)
  399.           break;
  400.       }
  401.       return res;
  402.     } else {
  403.       int res = inf;
  404.       for (int i = 0; i < sz(moves); ++i) {
  405.         board.ApplyMove(moves[i]);
  406.         int cur = Search(board, depth - 1, alpha, beta);
  407.         board.UndoMove(moves[i]);
  408.         if (res > cur) {
  409.           res = cur;
  410.           if (is_root)
  411.             best_move = moves[i];
  412.         }
  413.         if (res < beta)
  414.           beta = res;
  415.         if (beta <= alpha)
  416.           break;
  417.       }
  418.       return res;
  419.     }
  420.   }
  421.  
  422.   ScoringConfig scoring_config;
  423.   int max_depth;
  424.   double tl;
  425.   int max_moves;
  426.  
  427.   time_t start_time;
  428.   Move best_move;
  429. };
  430.  
  431. class MonteCarlo : public Strategy {
  432.  public:
  433.   struct Config {
  434.     ScoringConfig scoring_config;
  435.     double tl;
  436.     int playout_depth;
  437.     double exploration_coeff;
  438.     int expansion_threshold;
  439.     vector<int> playout_thresholds;
  440.     vector<int> num_moves;
  441.  
  442.     Config() : tl(0.9), playout_depth(5), exploration_coeff(0.3) {
  443.       expansion_threshold = 30;
  444.       playout_thresholds.pb(expansion_threshold - 1);
  445.       num_moves.pb(40);
  446.       playout_thresholds.pb(1000);
  447.       num_moves.pb(50);
  448.       playout_thresholds.pb(2000);
  449.       num_moves.pb(60);
  450.       playout_thresholds.pb(3000);
  451.       num_moves.pb(70);
  452.       playout_thresholds.pb(6000);
  453.       num_moves.pb(100);
  454.       playout_thresholds.pb(8000);
  455.       num_moves.pb(200);
  456.       playout_thresholds.pb(10000);
  457.       num_moves.pb(400);
  458.     }
  459.   };
  460.  
  461.   MonteCarlo() {}
  462.   MonteCarlo(Config config) : config(config) {}
  463.  
  464.   virtual Move GetMove(Board board) {
  465.     start_time = clock();
  466.     root = new Node(board, config);
  467.     int num_expands = 0;
  468.     while (clock() - start_time < config.tl * CLOCKS_PER_SEC) {
  469.       ExpandTree();
  470.       ++num_expands;
  471.     }
  472.     Move res;
  473.     double res_val = -1E100;
  474.     for (int i = 0; i < sz(root->kids); ++i) {
  475.       if (root->kids[i]->num_playouts == 0) continue;
  476.       double val = root->kids[i]->sum_scores / root->kids[i]->num_playouts;
  477.       if (root->board.player == 1) val = -val;
  478.       val -= sqrt(log(root->num_playouts) / root->kids[i]->num_playouts) * config.exploration_coeff;
  479.       if (val > res_val) {
  480.         res_val = val;
  481.         res = root->moves[i];
  482.       }
  483.     }
  484.     delete root;
  485.     return res;
  486.   }
  487.  
  488.  private:
  489.   struct Node {
  490.     Board board;
  491.     const Config& config;
  492.  
  493.     bool initialized;
  494.     vector<Move> moves;  // sorted
  495.     vector<Node*> kids;
  496.  
  497.     double num_playouts;
  498.     double sum_scores;
  499.  
  500.     Node(Board board, const Config& config)
  501.         : board(board), config(config), num_playouts(0), sum_scores(0),
  502.           initialized(false) {}
  503.  
  504.     ~Node() {
  505.       for (int i = 0; i < sz(kids); ++i)
  506.         delete kids[i];
  507.     }
  508.  
  509.     void Initialize() {
  510.       if (initialized)
  511.         return;
  512.       initialized = true;
  513.       vector<Move> raw_moves = board.GetAllMoves();
  514.       vector<pair<double, Move> > scored_moves;
  515.       for (int i = 0; i < sz(raw_moves); ++i) {
  516.         Move move = raw_moves[i];
  517.         board.ApplyMove(move);
  518.         double score = board.Score(config.scoring_config);
  519.         board.UndoMove(move);
  520.         if (board.player == 0)
  521.           score = -score;
  522.         scored_moves.pb(mp(score, move));
  523.       }
  524.       sort(all(scored_moves));
  525.       for (int i = 0; i < sz(scored_moves); ++i)
  526.         moves.pb(scored_moves[i].second);
  527.     }
  528.  
  529.     void Expand() {
  530.       Initialize();
  531.       int ind = 0;
  532.       while (ind < sz(config.playout_thresholds) &&
  533.              config.playout_thresholds[ind] <= num_playouts)
  534.         ++ind;
  535.       if (ind > 0)
  536.         --ind;
  537.       int cnt = config.num_moves[ind];
  538.       while (sz(kids) < cnt && sz(kids) < sz(moves)) {
  539.         Board new_board = board;
  540.         Move move = moves[sz(kids)];
  541.         new_board.ApplyMove(move);
  542.         kids.pb(new Node(new_board, config));
  543.       }
  544.     }
  545.  
  546.     double ExplorationExploitationScore(double total_playouts) {
  547.       double exploitation = sum_scores * (board.player == 0 ? -1 : 1) * 1.0 / num_playouts;
  548.       double exploration = sqrt(log(total_playouts) / num_playouts);
  549.       return exploration * config.exploration_coeff + exploitation;
  550.     }
  551.   };
  552.  
  553.   void ExpandTree() {
  554.     Node* cur_node = root;
  555.     vector<Node*> path;
  556.     path.pb(cur_node);
  557.     while (cur_node->num_playouts >= config.expansion_threshold) {
  558.       cur_node->Expand();
  559.       double total = 0.0;
  560.       for (int i = 0; i < sz(cur_node->kids); ++i)
  561.         total += cur_node->kids[i]->num_playouts;
  562.       Node* kid = NULL;
  563.       double kid_val = -1E100;
  564.       for (int i = 0; i < sz(cur_node->kids); ++i) {
  565.         Node* cur = cur_node->kids[i];
  566.         if (cur->num_playouts == 0) {
  567.           kid = cur;
  568.           kid_val = 1E100;
  569.           break;
  570.         }
  571.         double val = cur->ExplorationExploitationScore(total);
  572.         if (val > kid_val) {
  573.           kid = cur;
  574.           kid_val = val;
  575.         }
  576.       }
  577.       if (kid == NULL)
  578.         break;
  579.       cur_node = kid;
  580.       path.pb(cur_node);
  581.     }
  582.     int val = PlayOut(cur_node->board);
  583.     val = 1 - 2 * val;
  584.     for (int i = 0; i < sz(path); ++i) {
  585.       path[i]->num_playouts += 1;
  586.       path[i]->sum_scores += val;
  587.     }
  588.   }
  589.  
  590.   int PlayOut(Board board) {
  591.     for (int it = 0; it < config.playout_depth || board.player != 0; ++it) {
  592.       Move move = board.GetRandomMove();
  593.       if (!move.IsValid())
  594.         return 1 - board.player;
  595.       board.ApplyMove(move);
  596.     }
  597.     // Return player index.
  598.     return board.Score(config.scoring_config) > 0 ? 0 : 1;
  599.   }
  600.  
  601.   time_t start_time;
  602.   Node* root;
  603.   Config config;
  604. };
  605.  
  606. int PlayGame(Strategy* strategy1, Strategy* strategy2) {
  607.   Board board;
  608.   while (board.GetAllMoves().size() > 0) {
  609.     Move move = board.player == 0 ?
  610.         strategy1->GetMove(board) :
  611.         strategy2->GetMove(board);
  612.     board.ApplyMove(move);
  613.     cout << board.ToString() << "\n";
  614.   }
  615.   int res = 1 - board.player;
  616.   cout << "Winner: " << res << "\n";
  617.   return res;
  618. }
  619.  
  620. double Evaluate(Strategy* strategy1, Strategy* strategy2) {
  621.   double num = 0, den = 0;
  622.   RandomStrategy initial_strategy;
  623.   for (int it = 0; it < 100; ++it) {
  624.     Board board;
  625.     while (board.GetAllMoves().size() > 0) {
  626.       // Make the first several moves randomly.
  627.       if (board.move_index < 2) {
  628.         Move move = initial_strategy.GetMove(board);
  629.         board.ApplyMove(move);
  630.       } else {
  631.         Move move = (board.player + it * 1) % 2 == 0 ?
  632.             strategy1->GetMove(board) :
  633.             strategy2->GetMove(board);
  634.         board.ApplyMove(move);
  635.       }
  636.     }
  637.     int res = 1 - board.player;
  638.     if (it % 2 == 1) res = 1 - res;
  639.     num += 1.0 - res;
  640.     den += 1.0;
  641.     cerr << it << " " << res << "\n";
  642.     if ((it + 1) % 10 == 0)
  643.       cerr << "Iteration " << it << ": " << num / den << "\n";
  644.   }
  645.   return num / den;
  646. }
  647.  
  648. void StdinMove(Strategy* strategy) {
  649.   Board board;
  650.   for (int i = 0; i < N; ++i)
  651.     for (int j = 0; j < N; ++j) {
  652.       int c = i * N + j;
  653.       int x;
  654.       cin >> x;
  655.       if (x == 0)
  656.         board.field[c] = 0;
  657.       else if (x == 1)
  658.         board.field[c] = 1;
  659.       else if (x == 2)
  660.         board.field[c] = -1;
  661.       else
  662.         board.field[c] = -2;
  663.     }
  664.   int player;
  665.   cin >> player;
  666.   board.player = player == 1 ? 0 : 1;
  667.  
  668.   Move move = strategy->GetMove(board);
  669.   cout << move.x0 << " " << move.y0 << "\n";
  670.   cout << move.x1 << " " << move.y1 << "\n";
  671.   cout << move.x2 << " " << move.y2 << "\n";
  672. }
  673.  
  674. int main() {
  675.   srand(time(0));
  676.   RandomStrategy random_strategy;
  677.   ScoringConfig default_config;
  678.   GreedyDepth1 greedy(default_config);
  679.   AlphaBeta alpha_beta(default_config, 12, 0.5, 400);
  680.   MonteCarlo monte_carlo;
  681.   //PlayGame(&monte_carlo, &alpha_beta);
  682.   StdinMove(&monte_carlo);
  683.   //ScoringConfig old_config(1, 1);
  684.   //GreedyDepth1 greedy_old(old_config);
  685.   //MonteCarlo::Config new_config;
  686.   //new_config.scoring_config = ScoringConfig(16, 1);
  687.   //new_config.tl = 0.9;
  688.   //MonteCarlo monte_carlo_new(new_config);
  689.   //double res = Evaluate(&monte_carlo, &monte_carlo_new);
  690.   //cerr << "Val: " << res << "\n";
  691.   return 0;
  692. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!