Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.07 KB | None | 0 0
  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=32, 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 = 2; gg<cc; gg++){
  123.         int sx = g1(rnd), sy = g1(rnd), NUM_PICT = g2(rnd);
  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.             double dq_min = 1e100;
  138.             int px = -1, py = -1, best_pict = -1, pss=-1;
  139.             for (int ii = 0; ii < dq.size(); ii += 2) {
  140.                 int x = dq[ii], y = dq[ii+1];
  141.                 //inq[x][y] = 0;dq.pop_front();dq.pop_front();
  142.                 double bmn = 1e100;
  143.                 int num = -1, cn = x * k + y;
  144.                 for (int q = head; q <= k * k; q = nxt[q]) {
  145.                     int e = (x < k - 1 && us[x + 1][y]) +
  146.                             (y < k - 1 && us[x][y + 1]) +
  147.                             (x && us[x - 1][y]) +
  148.                             (y && us[x][y - 1]);
  149.                     double now =
  150.                             (x < k - 1 && us[x + 1][y] ? l[q - 1][2][ha[cn + k]] : 0) +
  151.                             (y < k - 1 && us[x][y + 1] ? l[q - 1][1][ha[cn + 1]] : 0) +
  152.                             (x && us[x - 1][y] ? l[q - 1][0][ha[cn - k]] : 0) +
  153.                             (y && us[x][y - 1] ? l[q - 1][3][ha[cn - 1]] : 0);
  154.                     now/=e;
  155.                     if (now < bmn) bmn = now, num = q;
  156.                 }
  157.                 if(bmn < dq_min) dq_min = bmn, px = x, py = y, best_pict = num, pss = ii;
  158.             }
  159.             inq[px][py] = 0;
  160.             dq.erase(dq.begin()+pss);
  161.             dq.erase(dq.begin()+pss);
  162.             if (best_pict == head) head = nxt[head];
  163.             nxt[pr[best_pict]] = nxt[best_pict];
  164.             pr[nxt[best_pict]] = pr[best_pict];
  165.             ha[px * k + py] = best_pict - 1;
  166.             us[px][py] = 1;
  167.             o += dq_min;
  168.             if (px && !us[px - 1][py] && !inq[px - 1][py]) dq.pb(px - 1), dq.pb(py), inq[px - 1][py] = 1;
  169.             if (py && !us[px][py - 1] && !inq[px][py - 1]) dq.pb(px), dq.pb(py - 1), inq[px][py - 1] = 1;
  170.             if (px + 1 < k && !us[px + 1][py] && !inq[px + 1][py]) dq.pb(px + 1), dq.pb(py), inq[px + 1][py] = 1;
  171.             if (py + 1 < k && !us[px][py + 1] && !inq[px][py + 1]) dq.pb(px), dq.pb(py + 1), inq[px][py + 1] = 1;
  172.         }
  173.         if(o<mn) mn = o, ans = ha;
  174.     }
  175.     //assert(ans.size()==k*k);
  176.     PER_ANS = ans;
  177. }
  178.  
  179. int main(){
  180.     fast;
  181.     lL = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
  182.     lA = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
  183.     lB = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
  184.     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;}
  185.     //for(int q=0; q<1000000; q++) sq[q] = sqrt(q), cb[q] = cbrt(q);
  186.     ofstream out_txt("C:\\Users\\BOG\\Desktop\\ANS16.txt");
  187.     for(int q=1800; q<1810; q++){
  188.         str PATH = "C:\\Users\\BOG\\Desktop\\data_test_int\\16\\";
  189.         str NAME = to_string(q)+".txt";
  190.         read(PATH+NAME);
  191.         work();
  192.         out_txt<<to_string(q)+".png"<<endl;
  193.         for(int i : PER_ANS) out_txt<<i<<" ";
  194.         out_txt<<endl;
  195.     }
  196. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement