fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <random>
  6. using namespace std;
  7. #define REP(i,a,b) for(int i=a;i<b;++i)
  8. #define rep(i,n) REP(i,0,n)
  9. typedef long long ll;
  10.  
  11. const int n=500;
  12. char A[n+32][n+32],B[n+32][n+32];
  13. #define a(r, c) A[r+9][c+9]
  14. #define b(r, c) B[r+9][c+9]
  15.  
  16. mt19937 engine;
  17. uniform_int_distribution<> rnd(0, n-1);
  18. ll p[1024];
  19. ll points[11];
  20. int v[3][9]={
  21.     {2, 0, 1, 5, 3, 4, 8, 6, 7},
  22.     {1, 2, 0, 4, 5, 3, 7, 8, 6},
  23.     {0, 1, 2, 3, 4, 5, 6, 7, 8},
  24. };
  25. ll checkRow(int r, int c)
  26. {
  27.     ll res=0; rep(i, 9) res|=1<<a(r, c+i); return p[res];
  28. }
  29. ll checkCol(int r, int c)
  30. {
  31.     ll res=0; rep(i, 9) res|=1<<a(r+i, c); return p[res];
  32. }
  33. ll check3x3(int r, int c)
  34. {
  35.     ll res=0; rep(i, 3) rep(j, 3) res|=1<<a(r+i, c+j); return p[res];
  36. }
  37. ll calcScore(int r, int c)
  38. {
  39.     ll res=0;
  40.     rep(i, 9) res+=checkRow(r, c-i);
  41.     rep(i, 9) res+=checkCol(r-i, c);
  42.     rep(i, 3) rep(j, 3) res+=check3x3(r-i, c-j);
  43.     return res;
  44. }
  45. int main(int argc, char**argv)
  46. {
  47.     clock_t start=clock();
  48.     points[1]=1; REP(i, 2, 10) points[i]=points[i-1]*45+1;
  49.     //REP(i, 1, 9) points[i]=0; points[9]=1;
  50.     rep(i, 1<<10) p[i]=points[__builtin_popcount(i)];
  51.  
  52.     rep(i, n) {
  53.         string s; cin>>s;
  54.         rep(j, n) {
  55.             a(i, j)=(s[j]=='0') ? (v[i%9/3][j%9]+3*i)%9+1 : s[j]-'0';
  56.             b(i, j)=s[j]-'0';
  57.         }
  58.     }
  59.  
  60.     int timelimit=atof(argv[1])*CLOCKS_PER_SEC;
  61.     int cnt=0;
  62.     while (true) {
  63.         int r, c;
  64.         do {
  65.             //r=(rand()>>10)%n; c=(rand()>>10)%n;
  66.             r=rnd(engine), c=rnd(engine);
  67.         } while (b(r, c));
  68.  
  69.         ll score=calcScore(r, c);
  70.         int t=a(r, c);
  71.         int maxx=t;
  72.         REP(x, 1, 10) if (x!=t) {
  73.             a(r, c)=x;
  74.             ll s=calcScore(r, c);
  75.             if (score <= s) { maxx=x; score=s; }
  76.         }
  77.         a(r, c)=maxx;
  78.         cnt++;
  79.         if (cnt%(1<<12)==0) if (clock()-start >= timelimit) break;
  80.     }
  81.  
  82.     cerr<<cnt<<endl;
  83.     rep(i, n) rep(j, n) if (b(i, j) && (b(i, j) != a(i, j))) {
  84.         cerr<<"INVALID"<<endl;
  85.         return 1;
  86.     }
  87.     rep(i, n) { rep(j, n) cout<<(int)a(i, j); cout<<endl; }
  88.  
  89.     return 0;
  90. }
Runtime error #stdin #stdout 0.01s 3864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/35yjxi
language:
C++14 (gcc 8.3)
created:
12 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!