Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma optimization_level 3
- #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
- #include<bits/stdc++.h>
- #define F first
- #define S second
- #define vec vector
- #define ms multiset
- #define pb push_back
- #define pll pair<ll,ll>
- #define pdd pair<ld, ld>
- #define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define pii pair<int, int>
- #define pnn pair<Node*, Node*>
- #define uid uniform_int_distribution
- #define FILE ifstream in("input.txt");ofstream out("output.txt");
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- using namespace std;
- typedef string str;
- typedef long long ll;
- typedef long double ld;
- typedef unsigned int uint;
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); //uid<int> u1(5, 10); u1(rnd);
- int a = 512, b = 512, k=32, d = 512/k;
- int R[512][512], G[512][512], B[512][512];
- //double cb[1000000], sq[1000000];
- vec<vec<vec<double>>> lL, lA, lB;
- vec<int> PER_ANS;
- void read(str FILE_NAME){
- ifstream in(FILE_NAME);
- cout<<FILE_NAME<<endl;
- for(int q=0; q<a; q++){
- for(int w=0; w<b; w++){
- int x; in>>x;
- G[q][w] = x&255; x>>=8;
- B[q][w] = x&255; x>>=8;
- R[q][w] = x&255;
- }
- }
- }
- struct LAB{
- double L, A, B;
- LAB(double sR, double sG, double sB) {
- double var_R = (sR / 255.0);
- double var_G = (sG / 255.0);
- double var_B = (sB / 255.0);
- if (var_R > 0.04045) var_R = pow(((var_R + 0.055) / 1.055), 2.4);
- else var_R = var_R / 12.92;
- if (var_G > 0.04045) var_G = pow(((var_G + 0.055) / 1.055), 2.4);
- else var_G = var_G / 12.92;
- if (var_B > 0.04045) var_B = pow(((var_B + 0.055) / 1.055), 2.4);
- else var_B = var_B / 12.92;
- var_R = var_R * 100;
- var_G = var_G * 100;
- var_B = var_B * 100;
- double X = var_R * 0.4124 + var_G * 0.3576 + var_B * 0.1805;
- double Y = var_R * 0.2126 + var_G * 0.7152 + var_B * 0.0722;
- double Z = var_R * 0.0193 + var_G * 0.1192 + var_B * 0.9505;
- double var_X = X / 100.000; //ref_X = 95.047 Observer= 2°, Illuminant= D65
- double var_Y = Y / 100.000; //ref_Y = 100.000
- double var_Z = Z / 100.000; //ref_Z = 108.883
- if (var_X > 0.008856) var_X = pow(var_X, (1. / 3.));
- else var_X = (7.787 * var_X) + (16. / 116.);
- if (var_Y > 0.008856) var_Y = pow(var_Y, (1. / 3.));
- else var_Y = (7.787 * var_Y) + (16. / 116.);
- if (var_Z > 0.008856) var_Z = pow(var_Z, (1. / 3.));
- else var_Z = (7.787 * var_Z) + (16. / 116.);
- L = (116. * var_Y) - 16.;
- A = 500. * (var_X - var_Y);
- B = 200. * (var_Y - var_Z);
- }
- };
- double col_dst(int &r1, int &g1, int &b1, int &r2, int &g2, int &b2){
- double ans = (lL[r1][g1][b1]-lL[r2][g2][b2])*(lL[r1][g1][b1]-lL[r2][g2][b2])
- + (lA[r1][g1][b1]-lA[r2][g2][b2])*(lA[r1][g1][b1]-lA[r2][g2][b2])
- + (lB[r1][g1][b1]-lB[r2][g2][b2])*(lB[r1][g1][b1]-lB[r2][g2][b2]);
- ans*=2*3.1415926535;
- return pow(ans, 0.22);
- }
- double pixel_diff(int x1, int y1, int x2, int y2){
- int r1 = R[x1][y1], g1 = G[x1][y1], b1 = B[x1][y1];
- int r2 = R[x2][y2], g2 = G[x2][y2], b2 = B[x2][y2];
- return col_dst(r1,g1,b1,r2,g2,b2);
- }
- double diff(int n1, int s1, int n2){
- int x1 = n1/k, y1 = n1%k, x2 = n2/k, y2 = n2%k;
- double o = 0;
- int sx1 = x1*d, sy1 = y1*d, sx2 = x2*d, sy2 = y2*d, dx=0, dy=0;
- if(s1==0){dy = 1; sx2 += d-1;}
- else if(s1==1){dx = 1; sy1 += d-1;}
- else if(s1==2){dy = 1; sx1 += d-1;}
- else{dx = 1; sy2+=d-1;}
- for(int g=0; g<d; g++, sx1+=dx, sy1+=dy, sx2+=dx, sy2+=dy){
- double c = pixel_diff(sx1,sy1,sx2,sy2);
- o+= c;
- }
- return o;
- }
- void work(){
- double mn = 1e200;
- vec<int> ans(k*k);
- vec<vec<vec<double>>> l(k*k, vec<vec<double>>(4, vec<double>(k*k)));
- 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);
- uid<int> g1(0, k-1), g2(0, k*k-1);
- vec<vec<int>> m(k*k, vec<int>(k*k));
- vec<int> nxt(k*k+2), pr(k*k+2);
- for(int gg=0, cc = 2; gg<cc; gg++){
- int sx = g1(rnd), sy = g1(rnd), NUM_PICT = g2(rnd);
- vec<int> ha = vec<int>(k*k, -1);
- ha[sx*k+sy] = NUM_PICT;
- deque<int> dq;
- vec<vec<int>> us(k, vec<int>(k)), inq(k, vec<int>(k));
- us[sx][sy] = 1;
- //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;
- 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;
- int head = NUM_PICT==0 ? 2 : 1;
- for(int q=0; q<k*k+2; q++) nxt[q] = q+1, pr[q] = q-1;
- nxt[NUM_PICT]++;
- pr[NUM_PICT+2]--;
- double o = 0;
- for(; dq.size() && o<mn;) {
- double dq_min = 1e100;
- int px = -1, py = -1, best_pict = -1, pss=-1;
- for (int ii = 0; ii < dq.size(); ii += 2) {
- int x = dq[ii], y = dq[ii+1];
- //inq[x][y] = 0;dq.pop_front();dq.pop_front();
- double bmn = 1e100;
- int num = -1, cn = x * k + y;
- for (int q = head; q <= k * k; q = nxt[q]) {
- int e = (x < k - 1 && us[x + 1][y]) +
- (y < k - 1 && us[x][y + 1]) +
- (x && us[x - 1][y]) +
- (y && us[x][y - 1]);
- double now =
- (x < k - 1 && us[x + 1][y] ? l[q - 1][2][ha[cn + k]] : 0) +
- (y < k - 1 && us[x][y + 1] ? l[q - 1][1][ha[cn + 1]] : 0) +
- (x && us[x - 1][y] ? l[q - 1][0][ha[cn - k]] : 0) +
- (y && us[x][y - 1] ? l[q - 1][3][ha[cn - 1]] : 0);
- now/=e;
- if (now < bmn) bmn = now, num = q;
- }
- if(bmn < dq_min) dq_min = bmn, px = x, py = y, best_pict = num, pss = ii;
- }
- inq[px][py] = 0;
- dq.erase(dq.begin()+pss);
- dq.erase(dq.begin()+pss);
- if (best_pict == head) head = nxt[head];
- nxt[pr[best_pict]] = nxt[best_pict];
- pr[nxt[best_pict]] = pr[best_pict];
- ha[px * k + py] = best_pict - 1;
- us[px][py] = 1;
- o += dq_min;
- if (px && !us[px - 1][py] && !inq[px - 1][py]) dq.pb(px - 1), dq.pb(py), inq[px - 1][py] = 1;
- if (py && !us[px][py - 1] && !inq[px][py - 1]) dq.pb(px), dq.pb(py - 1), inq[px][py - 1] = 1;
- if (px + 1 < k && !us[px + 1][py] && !inq[px + 1][py]) dq.pb(px + 1), dq.pb(py), inq[px + 1][py] = 1;
- if (py + 1 < k && !us[px][py + 1] && !inq[px][py + 1]) dq.pb(px), dq.pb(py + 1), inq[px][py + 1] = 1;
- }
- if(o<mn) mn = o, ans = ha;
- }
- //assert(ans.size()==k*k);
- PER_ANS = ans;
- }
- int main(){
- fast;
- lL = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
- lA = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
- lB = vec<vec<vec<double>>>(256, vec<vec<double>>(256, vec<double>(256)));
- 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;}
- //for(int q=0; q<1000000; q++) sq[q] = sqrt(q), cb[q] = cbrt(q);
- ofstream out_txt("C:\\Users\\BOG\\Desktop\\ANS16.txt");
- for(int q=1800; q<1810; q++){
- str PATH = "C:\\Users\\BOG\\Desktop\\data_test_int\\16\\";
- str NAME = to_string(q)+".txt";
- read(PATH+NAME);
- work();
- out_txt<<to_string(q)+".png"<<endl;
- for(int i : PER_ANS) out_txt<<i<<" ";
- out_txt<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement