SHARE
TWEET

Untitled

a guest Oct 13th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma optimization_level 3
  2. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
  3. #include<bits/stdc++.h>
  4. #define F first
  5. #define S second
  6. #define vec vector
  7. #define ms multiset
  8. #define pb push_back
  9. #define pll pair<ll,ll>
  10. #define pdd pair<ld, ld>
  11. #define pq priority_queue
  12. #define umap unordered_map
  13. #define uset unordered_set
  14. #define pii pair<int, int>
  15. #define pnn pair<Node*, Node*>
  16. #define uid uniform_int_distribution
  17. #define FILE ifstream in("input.txt");ofstream out("output.txt");
  18. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  19. using namespace std;
  20. typedef string str;
  21. typedef long long ll;
  22. typedef long double ld;
  23. typedef unsigned int uint;
  24. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); //uid<int> u1(5, 10); u1(rnd);
  25.  
  26. int a = 512, b = 512, k=16, d = 512/k;
  27. int R[512][512], G[512][512], B[512][512];
  28. double cb[1000000], sq[1000000];
  29. vec<vec<vec<double>>> lL, lA, lB;
  30. vec<int> PER_ANS;
  31.  
  32. void read(str FILE_NAME){
  33.     ifstream in(FILE_NAME);
  34.     cout<<FILE_NAME<<endl;
  35.     for(int q=0; q<a; q++){
  36.         for(int w=0; w<b; w++){
  37.             int x; in>>x;
  38.             G[q][w] = x&255; x>>=8;
  39.             B[q][w] = x&255; x>>=8;
  40.             R[q][w] = x&255;
  41.         }
  42.     }
  43. }
  44.  
  45. struct LAB{
  46.     double L, A, B;
  47.  
  48.     LAB(double sR, double sG, double sB) {
  49.         double var_R = (sR / 255.0);
  50.         double var_G = (sG / 255.0);
  51.         double var_B = (sB / 255.0);
  52.  
  53.         if (var_R > 0.04045) var_R = pow(((var_R + 0.055) / 1.055), 2.4);
  54.         else var_R = var_R / 12.92;
  55.         if (var_G > 0.04045) var_G = pow(((var_G + 0.055) / 1.055), 2.4);
  56.         else var_G = var_G / 12.92;
  57.         if (var_B > 0.04045) var_B = pow(((var_B + 0.055) / 1.055), 2.4);
  58.         else var_B = var_B / 12.92;
  59.  
  60.         var_R = var_R * 100;
  61.         var_G = var_G * 100;
  62.         var_B = var_B * 100;
  63.  
  64.         double X = var_R * 0.4124 + var_G * 0.3576 + var_B * 0.1805;
  65.         double Y = var_R * 0.2126 + var_G * 0.7152 + var_B * 0.0722;
  66.         double Z = var_R * 0.0193 + var_G * 0.1192 + var_B * 0.9505;
  67.  
  68.         double var_X = X / 100.000;         //ref_X =  95.047   Observer= 2°, Illuminant= D65
  69.         double var_Y = Y / 100.000;          //ref_Y = 100.000
  70.         double var_Z = Z / 100.000;          //ref_Z = 108.883
  71.  
  72.         if (var_X > 0.008856) var_X = pow(var_X, (1. / 3.));
  73.         else var_X = (7.787 * var_X) + (16. / 116.);
  74.         if (var_Y > 0.008856) var_Y = pow(var_Y, (1. / 3.));
  75.         else var_Y = (7.787 * var_Y) + (16. / 116.);
  76.         if (var_Z > 0.008856) var_Z = pow(var_Z, (1. / 3.));
  77.         else var_Z = (7.787 * var_Z) + (16. / 116.);
  78.  
  79.         L = (116. * var_Y) - 16.;
  80.         A = 500. * (var_X - var_Y);
  81.         B = 200. * (var_Y - var_Z);
  82.     }
  83. };
  84.  
  85. double col_dst(int &r1, int &g1, int &b1, int &r2, int &g2, int &b2){
  86.     double ans = (lL[r1][g1][b1]-lL[r2][g2][b2])*(lL[r1][g1][b1]-lL[r2][g2][b2])
  87.                           + (lA[r1][g1][b1]-lA[r2][g2][b2])*(lA[r1][g1][b1]-lA[r2][g2][b2])
  88.                           + (lB[r1][g1][b1]-lB[r2][g2][b2])*(lB[r1][g1][b1]-lB[r2][g2][b2]);
  89.     ans*=2*3.1415926535;
  90.     return pow(ans, 0.22);
  91. }
  92.  
  93. double pixel_diff(int x1, int y1, int x2, int y2){
  94.     int r1 = R[x1][y1], g1 = G[x1][y1], b1 = B[x1][y1];
  95.     int r2 = R[x2][y2], g2 = G[x2][y2], b2 = B[x2][y2];
  96.     return col_dst(r1,g1,b1,r2,g2,b2);
  97. }
  98.  
  99. double diff(int n1, int s1, int n2){
  100.     int x1 = n1/k, y1 = n1%k, x2 = n2/k, y2 = n2%k;
  101.     double o = 0;
  102.     int sx1 = x1*d, sy1 = y1*d, sx2 = x2*d, sy2 = y2*d, dx=0, dy=0;
  103.     if(s1==0){dy = 1; sx2 += d-1;}
  104.     else if(s1==1){dx = 1; sy1 += d-1;}
  105.     else if(s1==2){dy = 1; sx1 += d-1;}
  106.     else{dx = 1; sy2+=d-1;}
  107.     for(int g=0; g<d; g++, sx1+=dx, sy1+=dy, sx2+=dx, sy2+=dy){
  108.         double c = pixel_diff(sx1,sy1,sx2,sy2);
  109.         o+= c;
  110.     }
  111.     return o;
  112. }
  113.  
  114. void work(){
  115.     double mn = 1e200;
  116.     vec<int> ans(k*k);
  117.     vec<vec<vec<double>>> l(k*k, vec<vec<double>>(4, vec<double>(k*k)));
  118.     for(int q=0; q<k*k; q++) for(int w=0; w<4; w++) for(int e=0; e<k*k; e++) l[q][w][e] = diff(q,w,e);
  119.     uid<int> g1(0, k-1), g2(0, k*k-1);
  120.     vec<vec<int>> m(k*k, vec<int>(k*k));
  121.     vec<int> nxt(k*k+2), pr(k*k+2);
  122.     for(int gg=0, cc = k*k*k*k; gg<cc; gg++){
  123.         int sx = gg/k/k/k, sy = (gg/k/k)%k, NUM_PICT = gg%(k*k);
  124.         vec<int> ha = vec<int>(k*k, -1);
  125.         ha[sx*k+sy] = NUM_PICT;
  126.         deque<int> dq;
  127.         vec<vec<int>> us(k, vec<int>(k)), inq(k, vec<int>(k));
  128.         us[sx][sy] = 1;
  129.         //for(int q=sx-1; q>=0; q--) dq.pb(q), dq.pb(sy), inq[q][sy] = 1;for(int q=sx+1; q<k; q++) dq.pb(q), dq.pb(sy), inq[q][sy] = 1;for(int q=sy-1; q>=0; q--) dq.pb(sx), dq.pb(q), inq[sx][q] = 1;for(int q=sy+1; q<k; q++) dq.pb(sx), dq.pb(q), inq[sx][q] = 1;
  130.         if(sx) dq.pb(sx-1), dq.pb(sy), inq[sx-1][sy] = 1;if(sy) dq.pb(sx), dq.pb(sy-1), inq[sx][sy-1] = 1;if(sx+1<k) dq.pb(sx+1), dq.pb(sy), inq[sx+1][sy] = 1;if(sy+1<k) dq.pb(sx), dq.pb(sy+1), inq[sx][sy+1] = 1;
  131.         int head = NUM_PICT==0 ? 2 : 1;
  132.         for(int q=0; q<k*k+2; q++) nxt[q] = q+1, pr[q] = q-1;
  133.         nxt[NUM_PICT]++;
  134.         pr[NUM_PICT+2]--;
  135.         double o = 0;
  136.         for(; dq.size() && o<mn;){
  137.             int x = dq[0], y = dq[1];
  138.             inq[x][y] = 0;
  139.             dq.pop_front();
  140.             dq.pop_front();
  141.             double bmn = 1e100, uu = 1e100;
  142.             int num = -1, cn = x*k+y;
  143.             for(int q=head; q<=k*k; q = nxt[q]){
  144.                 double now =
  145.                         (x<k-1 && us[x+1][y] ? l[q-1][2][ha[cn+k]] : 0) +
  146.                         (y<k-1 && us[x][y+1] ? l[q-1][1][ha[cn+1]] : 0) +
  147.                         (x && us[x-1][y] ? l[q-1][0][ha[cn-k]] : 0) +
  148.                         (y && us[x][y-1] ? l[q-1][3][ha[cn-1]] : 0);
  149.                 if (now < bmn) bmn = now, num = q, uu = now;
  150.             }
  151.             if(num==head) head = nxt[head];
  152.             nxt[pr[num]] = nxt[num];
  153.             pr[nxt[num]] = pr[num];
  154.             ha[x*k+y] = num-1;
  155.             us[x][y] = 1;
  156.             o+=uu;
  157.             if(x && !us[x-1][y] && !inq[x-1][y]) dq.pb(x-1), dq.pb(y), inq[x-1][y] = 1;
  158.             if(y && !us[x][y-1] && !inq[x][y-1]) dq.pb(x), dq.pb(y-1), inq[x][y-1] = 1;
  159.             if(x+1<k && !us[x+1][y] && !inq[x+1][y]) dq.pb(x+1), dq.pb(y), inq[x+1][y] = 1;
  160.             if(y+1<k && !us[x][y+1] && !inq[x][y+1]) dq.pb(x), dq.pb(y+1), inq[x][y+1] = 1;
  161.         }
  162.  
  163.         if(o<mn) mn = o, ans = ha;
  164.     }
  165.     PER_ANS = ans;
  166. }
  167.  
  168. int main(){
  169.     fast;
  170.     lL = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
  171.     lA = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
  172.     lB = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
  173.     for(int q=0; q<256; q++) for(int w=0; w<256; w++) for(int e=0; e<256; e++){LAB x(q,w,e);lL[q][w][e] = x.L;lA[q][w][e] = x.A;lB[q][w][e] = x.B;}
  174.     for(int q=0; q<1000000; q++) sq[q] = sqrt(q), cb[q] = cbrt(q);
  175.     ofstream out_txt("C:\\Users\\BOG\\Desktop\\ANS32.txt");
  176.     for(int q=2110; q<2400; q++){
  177.         str PATH = "C:\\Users\\BOG\\Desktop\\data_test_int\\32\\";
  178.         str NAME = to_string(q)+".txt";
  179.         read(PATH+NAME);
  180.         work();
  181.         out_txt<<to_string(q)+".png"<<endl;
  182.         for(int i : PER_ANS) out_txt<<i<<" ";
  183.         out_txt<<endl;
  184.     }
  185. }
RAW Paste Data
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
 
Top