fork download
copy 
  1. // g++ -O3 -std=c++0x iterative_o3.cc
  2. // ./a.out < testcase.txt
  3. // cat result.txt
  4. #include <iostream>
  5. #include <fstream>
  6. #include <string>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <random>
  11. #include <assert.h>
  12. #include <sys/time.h>
  13. #include <stdint.h>
  14.  
  15. using namespace std;
  16. const int N = 500;
  17. typedef long long LL;
  18.  
  19. class Timer{
  20. protected:
  21.     double startTime;
  22. public:
  23.     Timer(){ startTime = now(); }
  24.     double elapse(){ return now() - startTime; }
  25. protected:
  26.     double now(){
  27.         timeval tv;
  28.         gettimeofday(&tv, 0);
  29.         return tv.tv_sec + tv.tv_usec * 1e-6;
  30.     }
  31. };
  32.  
  33. template <class T>
  34. struct Matrix{
  35.     T data[N*N];
  36.     Matrix(){}
  37.     Matrix(const T& init){
  38.         for(int y = 0;y < N; y++){
  39.             for(int x = 0;x < N; x++){
  40.                 data[y*N+x] = init;
  41.             }
  42.         }
  43.     }
  44.     const T* operator[](int y) const{
  45.         return &(data[y*N]);
  46.     }
  47.     T* operator[](int y){
  48.         return &(data[y*N]);
  49.     }
  50. };
  51.  
  52. Timer timer;
  53. Matrix<int> preset;
  54. Matrix<int> board;
  55.  
  56. mt19937_64 mt19937_obj;
  57. LL myrand(){
  58.     return mt19937_obj() >> 1;
  59. }
  60.  
  61. template <class T>
  62. void shuffle(T b, T e){
  63.     while(b != e){
  64.         T t = b + myrand() % (e-b);
  65.         swap(*t, *b);
  66.         b++;
  67.     }
  68. }
  69.  
  70. void initialize(){
  71.     for(int y = 0; y < N; y++){
  72.         for(int x = 0; x < N; x++){
  73.             if(preset[y][x]) continue;
  74.             board[y][x] = 1<<(myrand()%9+1);
  75.         }
  76.     }
  77. }
  78.  
  79. int calcScore(const Matrix<int>& board);
  80. void writeBoard(const Matrix<int>& board, ostream& st){
  81.     for(int y = 0; y < N; y++){
  82.         for(int x = 0; x < N; x++){
  83.             int v = 1;
  84.             for(int i = 1; i <= 9; i++){
  85.                 if(board[y][x] == (1<<i)) v = i;
  86.             }
  87.             st << v;
  88.         }
  89.         st << endl;
  90.     }
  91.     st << endl;
  92.     st << "score : " << calcScore(board) << endl;
  93.     st << "elapse : " << timer.elapse() << endl;
  94. }
  95.  
  96. void writeBoard(const Matrix<int>& board, const char* filename){
  97.     ofstream st(filename);
  98.     writeBoard(board, st);
  99. }
  100.  
  101. void readBoard(Matrix<int>& board, istream& st){
  102.     for(int y = 0; y < N; y++){
  103.         string line;
  104.         st >> line;
  105.         for(int x = 0; x < N; x++){
  106.             int n = line[x]-'0';
  107.             if(n == 0){
  108.                 board[y][x] = 0;
  109.             }else{
  110.                 board[y][x] = 1<<n;
  111.             }
  112.             if(preset[y][x]) assert(preset[y][x] == board[y][x]);
  113.         }
  114.     }
  115. }
  116.  
  117. void readBoard(Matrix<int>& board, const char* filename){
  118.     ifstream st(filename);
  119.     readBoard(board, st);
  120. }
  121.  
  122. int lineScoreH(const Matrix<int>& board, int x, int y, int ex){
  123.     int state = 0;
  124.     int score = 0;
  125.     for(int i = 0; i < 8; i++, x++){
  126.         state += board[y][x];
  127.     }
  128.     for(; x < ex; x++){
  129.         state += board[y][x];
  130.         if(state == 0x3fe) score++;
  131.         state -= board[y][x-8];
  132.     }
  133.     return score;
  134. }
  135.  
  136. int lineScoreV(const Matrix<int>& board, int x, int y, int ey){
  137.     int state = 0;
  138.     int score = 0;
  139.     for(int i = 0; i < 8; i++, y++){
  140.         state += board[y][x];
  141.     }
  142.     for(; y < ey; y++){
  143.         state += board[y][x];
  144.         if(state == 0x3fe) score++;
  145.         state -= board[y-8][x];
  146.     }
  147.     return score;
  148. }
  149.  
  150. int blockScore(const Matrix<int>& board, int y, int sx, int ex){
  151.     if(y+2 >= N) return 0;
  152.     int state = 0;
  153.     int score = 0;
  154.     int x = sx;
  155.     for(; x < sx+2; x++){
  156.         state += board[y+0][x];
  157.         state += board[y+1][x];
  158.         state += board[y+2][x];
  159.     }
  160.     for(; x < ex; x++){
  161.         state += board[y+0][x];
  162.         state += board[y+1][x];
  163.         state += board[y+2][x];
  164.         if(state == 0x3fe) score++;
  165.         state -= board[y+0][x-2];
  166.         state -= board[y+1][x-2];
  167.         state -= board[y+2][x-2];
  168.     }
  169.     return score;
  170. }
  171.  
  172. int calcScore(const Matrix<int>& board){
  173.     int score = 0;
  174.     for(int y = 0; y < N; y++){
  175.         score += lineScoreH(board, 0, y, N);
  176.         score += lineScoreV(board, y, 0, N);
  177.     }
  178.     for(int y = 0; y+2 < N; y++){
  179.         score += blockScore(board, y, 0, N);
  180.     }
  181.     return score;
  182. }
  183.  
  184. int partialScore(Matrix<int>& board, int x, int y){
  185.     int score = 0;
  186.     score += lineScoreH(board, max(0,x-8), y, min(N,x+9));
  187.     score += lineScoreV(board, x, max(0,y-8), min(N,y+9));
  188.     for(int y2 = max(0,y-2); y2 <= y; y2++){
  189.         score += blockScore(board, y2, max(0,x-2), min(N,x+3));
  190.     }
  191.     return score;
  192. }
  193.  
  194. const int one_left_tbl[] = {1<<5,1<<6,1<<3,1<<7,1<<9,1<<4,1<<2,1<<8,1<<1,0,0};
  195. const int one_left_tbl_width = 11;
  196.  
  197. struct OneLeft{
  198.     int16_t x;
  199.     int16_t y;
  200.     int to_be;
  201.     OneLeft(){}
  202.     OneLeft(int x_, int y_, int to_be_):x(x_),y(y_),to_be(to_be_){}
  203. };
  204.  
  205. void getOneLeftLineH(const Matrix<int>& board, int x, int y, vector<OneLeft>& res){
  206.     int cnt = 0;
  207.     int cnt2 = 0;
  208.     for(int i = 0; i < 9; i++){
  209.         cnt |= board[y][x+i];
  210.         cnt2 ^= board[y][x+i];
  211.     }
  212.     int to_be = one_left_tbl[cnt % one_left_tbl_width];
  213.     if((cnt | to_be) != 0x3fe) return;
  214.     int v = one_left_tbl[(cnt2|to_be) % one_left_tbl_width];
  215.     for(int i = 0; i < 9; i++){
  216.         if(board[y][x+i] == v && !preset[y][x+i]){
  217.             res.push_back(OneLeft(x+i, y, to_be));
  218.         }
  219.     }
  220. }
  221.  
  222. void getOneLeftLineV(const Matrix<int>& board, int x, int y, vector<OneLeft>& res){
  223.     int cnt = 0;
  224.     int cnt2 = 0;
  225.     for(int y2 = y; y2 < y+9; y2++){
  226.         cnt |= board[y2][x];
  227.         cnt2 ^= board[y2][x];
  228.     }
  229.     int to_be = one_left_tbl[cnt % one_left_tbl_width];
  230.     if((cnt | to_be) != 0x3fe) return;
  231.     int v = one_left_tbl[(cnt2|to_be) % one_left_tbl_width];
  232.     for(int y2 = y; y2 < y+9; y2++){
  233.         if(board[y2][x] == v && !preset[y2][x]){
  234.             res.push_back(OneLeft(x, y2, to_be));
  235.         }
  236.     }
  237. }
  238.  
  239. void getOneLeftBlock(const Matrix<int>& board, int x, int y, vector<OneLeft>& res){
  240.     int cnt = 0;
  241.     int cnt2 = 0;
  242.     for(int y2 = y; y2 < y+3; y2++){
  243.         cnt |= board[y2][x+0];
  244.         cnt2 ^= board[y2][x+0];
  245.         cnt |= board[y2][x+1];
  246.         cnt2 ^= board[y2][x+1];
  247.         cnt |= board[y2][x+2];
  248.         cnt2 ^= board[y2][x+2];
  249.     }
  250.     int to_be = one_left_tbl[cnt % one_left_tbl_width];
  251.     if((cnt | to_be) != 0x3fe) return;
  252.     int v = one_left_tbl[(cnt2|to_be) % one_left_tbl_width];
  253.     for(int y2 = y; y2 < y+3; y2++){
  254.         for(int dx = 0; dx < 3; dx++){
  255.             if(board[y2][x+dx] == v && !preset[y2][x+dx]){
  256.                 res.push_back(OneLeft(x+dx, y2, to_be));
  257.             }
  258.         }
  259.     }
  260. }
  261.  
  262. void getOneLeft(const Matrix<int>& board, int x, int y, vector<OneLeft>& res){
  263.     for(int x2 = max(0,x-8); x2 <= min(x, N-9); x2++){
  264.         getOneLeftLineH(board, x2, y, res);
  265.     }
  266.     for(int y2 = max(0,y-8); y2 <= min(y, N-9); y2++){
  267.         getOneLeftLineV(board, x, y2, res);
  268.     }
  269.     for(int x2 = max(0,x-2); x2 <= min(x, N-3); x2++){
  270.         for(int y2 = max(0,y-2); y2 <= min(y, N-3); y2++){
  271.             getOneLeftBlock(board, x2, y2, res);
  272.         }
  273.     }
  274. }
  275.  
  276. int rollbackHistory(Matrix<int>& board, vector<pair<int,int> >& history, int history_idx, int score){
  277.     if(history.empty()) return score;
  278.     for(int i = history.size()-1; i >= history_idx; i--){
  279.         int x2 = history[i].first % N;
  280.         int y2 = history[i].first / N;
  281.         board[y2][x2] = history[i].second >> 20;
  282.     }
  283.     score = history[history_idx].second & ((1<<20)-1);
  284.     history.resize(history_idx);
  285.     return score;
  286. }
  287.  
  288. static int HASH_W = 29;
  289. uint64_t updateHash(uint64_t hash, int x,  int y, int n){
  290.     return hash ^ (0x510990bf819745cLL / (((x * 500 + y) << 10) + n+1));
  291. }
  292.  
  293. int search_best = 0;
  294. int search(Matrix<int>& board, int x, int y, int depth, int score, int best, vector<pair<int,int> >& history, uint64_t hash, vector<int>& memo, const int hash_v){
  295.     //if(depth > 15) return score;
  296.     if(depth > 10) return score;
  297.     if(score < search_best - 25) return score;
  298.  
  299.     int search_w = 4;
  300.     vector<OneLeft> one_left;
  301.     one_left.reserve(250);
  302.     getOneLeft(board, x, y, one_left);
  303.     shuffle(one_left.begin(), one_left.end());
  304.     int history_idx = history.size();
  305.     for(int i = 0; i < search_w && i < one_left.size(); i++){
  306.         int x2 = one_left[i].x;
  307.         int y2 = one_left[i].y;
  308.         int n = one_left[i].to_be;
  309.         if(preset[y2][x2] || board[y2][x2]==n) continue;
  310.         if(x2==x && y2==y && depth > 0){
  311.             search_w++;
  312.             continue;
  313.         }
  314.         if(depth == 0 && (x2!=x || y2!=y)){
  315.             search_w++;
  316.             continue;
  317.         }
  318.         uint64_t new_hash = updateHash(hash, x2, y2, n);
  319.         if(memo[new_hash & ((1ULL<<HASH_W)-1)] == hash_v){
  320.             continue;
  321.         }
  322.         int history_idx2 = history.size();
  323.         history.push_back(pair<int,int>(y2*N+x2, score+(board[y2][x2]<<20)));
  324.         int org_score = score;
  325.         int prev_score = partialScore(board, x2, y2);
  326.         board[y2][x2] = n;
  327.         int new_score = partialScore(board, x2, y2);
  328.         score += new_score - prev_score;
  329.         score = search(board, x2, y2, depth+1, score, best, history, new_hash, memo, hash_v);
  330.         if(score < org_score){
  331.             score = rollbackHistory(board, history, history_idx2, score);
  332.             // memory no changes
  333.             memo[new_hash & ((1ULL<<HASH_W)-1)] = hash_v;
  334.         }else{
  335.             hash = new_hash;
  336.         }
  337.     }
  338.     return score;
  339. }
  340.  
  341. int search(Matrix<int>& board, int x, int y, int best, vector<int>& memo, const int hash_v){
  342.     search_best = best;
  343.     vector<pair<int,int> > history;
  344.     history.reserve(4090);
  345.     int score = search(board, x, y, 0, best, best, history, 0, memo, hash_v);
  346.     if(score < best){
  347.         score = rollbackHistory(board, history, 0, score);
  348.     }
  349.     return score;
  350. }
  351.  
  352. void optimize(){
  353.     initialize();
  354.     int best = calcScore(board);
  355.     int e2 = 0;
  356.     while(true){
  357.         vector<int> memo(1ULL<<HASH_W);
  358.         for(int y = 0; y < N; y++){
  359.             for(int x = 0; x < N; x++){
  360.                 best = search(board, x, y, best, memo, x+y*N);
  361.             }
  362.             cerr << e2 << " : " << y << " , " << best << " , " << timer.elapse() << endl;
  363.         }
  364.         writeBoard(board, "result.txt");
  365.         assert(best == calcScore(board));
  366.         e2++;
  367.     }
  368. }
  369.  
  370. int main(){
  371.     readBoard(board, cin);
  372.     preset = board;
  373.     optimize();
  374.     return 0;
  375. }
  376.  
Runtime error #stdin #stdout #stderr 0s 6288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/lNaoKH
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!