#define BUFSIZE 1000000 int Tests, cnum; // #define USEWIN #define MANYTESTS 0 // #define LINEBYLINE #include #include #include #include #include #include #include #include using namespace std; void ansicol16(int col, FILE *f = stdout) { int coltab[16] = { 30, 34, 32, 36, 31, 35, 33, 37, 30, 34, 32, 36, 31, 35, 33, 37 }; fprintf(f, "\033[%d;%dm", col >= 8 ? 1 : 2, coltab[col]); } void ansiclear(FILE *f = stdout) { fprintf(f, "\033[0m"); } typedef long long ll; #define LS < #define Size(x) (int(x.size())) #define LET(k,val) __typeof(val) k = (val) // execute "act", and return "val" as an expression result #define CLC(act,val) ([&] () {act; return (val); } ()) // All macros with parameters "k,a,b" run the "k" variable in range [a,b) #define FOR(k,a,b) for(__typeof(a) k=(a); k LS (b); ++k) // find the first k in [a,b) that satisfies cond, or b if none #define FIRST(k,a,b,cond) CLC(LET(k, a); for(; k LS (b); ++k) if(cond) break, k) #define INF 500000000 // Bit Count int bitc(ll r) {return r == 0 ? 0 : (bitc(r>>1) + (r&1));} // int to string string its(int i) {char buf[200]; sprintf(buf, "%d", i); return buf;} string getLine() { string s; while(!feof(stdin)) { char c = fgetc(stdin); if(c == 13) continue; if(c == 10) return s; s += c; } return s; } int scanerr; int getNum() { #ifdef LINEBYLINE string s = getLine(); return atoi(s.c_str()); #else int i; scanerr = scanf("%d", &i); return i; #endif } #ifndef BUFSIZE #define BUFSIZE 1000000 #endif char buf[BUFSIZE]; #include ll getVa() { struct timeval tval; gettimeofday(&tval, NULL); return tval.tv_sec * 1000000 + tval.tv_usec; } #line 9 "work.cpp" #include // ---- TEMPLATE ENDS HERE ---- //Eryx // input limits //-------------- #define MAXSON 32 #define MAXBOARD 64 #define MAXBOARD2 (MAXBOARD*MAXBOARD) int X, Y, K; // actual parameters // cell encoding //--------------- // we encode a pair of coordinates with a single number; coordinates are 1-based // (zeros are used as guards) #define XY(x,y) ((y)*MAXBOARD+x) #define GETX(xy) (xy&(MAXBOARD-1)) #define GETY(xy) ((int)(((unsigned)xy)/MAXBOARD)) #define GETXY(xy) GETX(xy), GETY(xy) // cardinal directions are represented as: const int dxy[16] = { 1,MAXBOARD,-1,-MAXBOARD, 1,MAXBOARD,-1,-MAXBOARD, 1,MAXBOARD,-1,-MAXBOARD, 1,MAXBOARD,-1,-MAXBOARD, }; // eight directions are represented as: const int dxy8[8] = { MAXBOARD-1, MAXBOARD, MAXBOARD+1, 1, 1-MAXBOARD, -MAXBOARD, -1-MAXBOARD, -1 }; int pxy[2][MAXSON]; // positions of fountains (0,1 -- indices) char kmap[MAXBOARD2]; // current map char cetype[MAXBOARD2]; // cell type: 0,1 -- fountain, 2 - empty int cid[MAXBOARD2]; // fountain id int tryindex = 0; // how many tries so far int curtime; // time elapsed so far double bestscore; // best score so far char bestmap[MAXBOARD2]; // best map found so far // other basics //-------------- // exception (I simulate exceptions with bool excthrown because I got weird // errors when I have been using exceptions -- these turned out to not be // actually related to exceptions, but the simulation remains) bool excthrown; // a function to display the current state nicely void debugshot(); // score and connectivity handling //--------------------------------- int area[MAXSON]; // area for each son int perim[MAXSON]; // perimeter for each son double cursc; // current score for local search void calcap(); // compute area and perim double compscore(); // compute the current score void swtch(int xy, char c); // switch the location xy to group c, ancknowledge in area/perim double getscore() { calcap(); return compscore(); } void calcap() { for(int k=0; k= K) continue; area[id]++; FOR(d,0,4) if(kmap[xy+dxy[d]] != c) perim[id]++; } } void ack(char we, char them, int delta) { if(we == them) return; int id = we - 'a'; if(id < 0 || id >= K) return; perim[id] += delta; } void ack4(int xy, int delta) { area[kmap[xy]-'a'] += delta; FOR(d,0,4) { int xy0 = xy + dxy[d]; ack(kmap[xy], kmap[xy0], delta); ack(kmap[xy0], kmap[xy], delta); } } void swtch(int xy, char c) { ack4(xy, -1); kmap[xy] = c; ack4(xy, +1); } double compscore() { double res = 0; FOR(k,0,K) res += area[k] / pow(perim[k], 2); res /= K; res *= 160000; return res; } // verify connectivity //--------------------- void floodfill(int xy, char c) { if(kmap[xy] != '.') return; kmap[xy] = c; FOR(d,0,4) floodfill(xy + dxy[d], c); } void vercon(int xy, int v) { if(kmap[xy] != v) return; kmap[xy] = -kmap[xy]; FOR(d,0,4) vercon(xy + dxy[d], v); } char allgroups[32]; bool vercon() { int groups = 0; FOR(y,1,Y+1) FOR(x,1,X+1) { int xy = XY(x,y); if(kmap[xy] > 0) allgroups[groups++] = kmap[xy], vercon(xy, kmap[xy]); } FOR(y,1,Y+1) FOR(x,1,X+1) { int xy = XY(x,y); if(kmap[xy] < 0) kmap[xy] = -kmap[xy]; } return groups == K; } // FIRST PHASE: connect pairs // -------------------------- // Rough idea: we use the hungarian method to connect pairs of fountains, // then we use Dijkstra algorithm to connect pairs returned by hungarian method // with paths, starting from the closest one. If it is impossible to connect // a pair, one (or more) of the older paths is removed, squares on this path // are given an extra penalty cost, and possibly // assignments are switched. // implementation of the hungarian algorithm (pre-written) #define MAXIT MAXSON #define MAXBID MAXSON namespace hungarian { #define PHI -1 #define NOL -2 int items, bidders; int w[MAXIT][MAXBID]; bool x[MAXIT][MAXBID]; int asg[MAXIT]; void hungarian() { bool ss[MAXIT]; bool st[MAXBID]; int u[MAXIT]; int v[MAXBID]; int p[MAXBID]; int ls[MAXIT]; int lt[MAXBID]; int f = 0; FOR(i,0,items) FOR(j,0,bidders) f = max(f, w[i][j]); FOR(i,0,items) FOR(j,0,bidders) x[i][j] = false; FOR(i,0,items) u[i] = f, ls[i] = PHI, ss[i] = false; FOR(j,0,bidders) v[j] = 0, p[j] = INF, lt[j] = NOL, st[j] = false; while(true) { f = -1; FOR(i, 0, items) if(ls[i] != NOL && !ss[i]) { f = i; break; } if(f != -1) { ss[f] = true; FOR(j, 0, bidders) if(!x[f][j] && u[f] + v[j] - w[f][j] < p[j]) { lt[j] = f; p[j] = u[f] + v[j] - w[f][j]; } } else { FOR(j, 0, bidders) if(lt[j] != NOL && !st[j] && p[j] == 0) { f = j; break; } if(f == -1) { int d1 = INF, d2 = INF, d; FOR(i, 0, items) d1 = min(d1, u[i]); FOR(j, 0, bidders) if(p[j] > 0) d2 = min(d2, p[j]); d = min(d1, d2); FOR(i, 0, items) if(ls[i] != NOL) u[i] -= d; FOR(j, 0, bidders) { if(p[j] == 0) v[j] += d; if(p[j] > 0 && lt[j] != NOL) p[j] -= d; } if(d2 >= d1) break; } else { st[f] = true; int s = -1; for(int i = 0; i < items && s == -1; i++) if(x[i][f]) s = i; if(s == -1) { int r = f; while(true) { int l = lt[r]; if(l < 0) break; x[l][r] = !x[l][r]; r = ls[l]; if(r < 0) break; x[l][r] = !x[l][r]; } FOR(i,0,items) ls[i] = PHI, ss[i] = false; FOR(j,0,bidders) p[j] = INF, lt[j] = NOL, st[j] = false; FOR(i,0,items) { FOR(j,0,bidders) if(x[i][j]) { ls[i] = NOL; break; } } } else { ls[s] = f; } } } } FOR(i,0,items) { asg[i] = -1; FOR(j,0,bidders) if(x[i][j]) asg[i] = j; } } } typedef vector path; path paths[MAXSON]; // the path used by each son bool gotit[MAXSON]; // have we already connected the pair int val[MAXSON]; // the value of each pair -- pairs with higher value are placed first int ngotit; // number of connected pairs (sum of gotit) vector pathsremoved; // paths we have recently removed int failedon[MAXSON]; // here we count the number of tries we failed to connect each pair // use the hungarian method to find pairs, also set val's void useHungarian() { FOR(k0,0,K) FOR(k1,0,K) hungarian::w[k0][k1] = int(10000 - 100 * hypot(GETY(pxy[0][k0])-GETY(pxy[1][k1]), GETX(pxy[0][k0])-GETX(pxy[1][k1]))); hungarian::hungarian(); if(curtime > (bestscore > 0 ? 1500000 : 1700000)) { int reroutes = rand() % 10; for(int i=0; i> pq; pq.emplace(0, sxy); while(!pq.empty()) { auto ent = pq.top(); pq.pop(); int xy = ent.second; #if 0 if(x<=0 || y<=0 || x > X || y > Y) { #ifdef LOCAL printf("got out!\n"); FOR(y,0,Y+2) { FOR(x,0,X+2) printf("%6d", min(bfsmap[y][x], 999999)); printf("\n"); } printf("\n"); FOR(y,0,Y+2) { FOR(x,0,X+2) printf("%6d", min(costmap[y][x], 999999)); printf("\n"); } printf("\n"); #endif excthrown = true; return; } #endif int val = -ent.first; if(bfsmap[xy] < val) continue; bfsmap[xy] = val; if(xy==txy) goto reached; for(int d=0; d<4; d++) { int xy1 = xy+dxy[d]; int nval = val + costmap[xy1]; if(bfsmap[xy1] > nval) { bfsmap[xy1] = nval; pq.emplace(-nval, xy1); } } } #ifdef LOCAL printf("could not reach %d -> %d\n", sxy, txy); FOR(y,0,Y+2) { FOR(x,0,X+2) printf("%6d", min(bfsmap[y*MAXBOARD+x], 999999)); printf("\n"); } printf("\n"); FOR(y,0,Y+2) { FOR(x,0,X+2) printf("%6d", min(costmap[y*MAXBOARD+x], 999999)); printf("\n"); } printf("\n"); #endif excthrown = true; return; reached: int xeach = abs(GETX(sxy)-GETX(txy)); int tsteps = xeach + abs(GETY(sxy)-GETY(txy)); int v = rand() % tsteps; while(true) { p.emplace_back(txy); if(bfsmap[txy] == 0) break; bool wd = false; v += xeach; if(v >= tsteps) v -= tsteps; else wd = true; for(int d0=0; d0<4; d0++) { int d = d0; if(wd) d ^= 1; int xy1 = txy+dxy[d]; if(bfsmap[xy1] == bfsmap[txy] - costmap[txy]) { txy = xy1; goto nextstep; } } #ifdef LOCAL printf("failed while connecting (%d,%d cost=%d bfs=%d) \n", GETXY(txy), costmap[txy], bfsmap[txy]); for(int d0=0; d0<4; d0++) { int d = d0; int xy1 = txy+dxy[d]; printf("-> %d\n", bfsmap[xy1]); } FOR(y,0,Y+2) { FOR(x,0,X+2) { int xy = XY(x,y); if(xy==txy) ansicol16(12); if(xy==sxy) ansicol16(10); printf("%6d", min(bfsmap[xy]/100, 999999)); ansiclear(); } printf("\n"); } exit(1); #endif // debugshot(); excthrown = true; return; // throw failed0; nextstep: ; } } void removepath(int id) { // printf("removing path %d of size %d\n", id, Size(paths[id])); pathsremoved.push_back(id); char c = id + 'a'; path& p = paths[id]; gotit[id]=0; ngotit--; int penalty = PENALTY / Size(p); for(auto& xy: p) { kmap[xy] = '.'; costmap[xy] -= CROSSCOST; costmap[xy] += penalty; } if(0) FOR(y,0,Y+2) { FOR(x,0,X+2) printf("%6d", min(costmap[XY(x,y)], 999999)); printf("\n"); } } void placepath(int id) { char c = id + 'a'; path& p = paths[id]; gotit[id]=true; ngotit++; for(auto& xy: p) { if(kmap[xy] != '.') removepath(kmap[xy] - 'a'); kmap[xy] = c; costmap[xy] += CROSSCOST; } } // SECOND PHASE: fill the remaining squares //------------------------------------------ // angle fill: if two adjacent square are owned by the same son, // we are also owned by this son void anglefill(int xy) { if(kmap[xy] != '.') return; for(int d=0; d<4; d++) { int d0 = d+1; char c = kmap[xy+dxy[d]]; if(c && c != '.' && c == kmap[xy+dxy[d0]]) { kmap[xy] = c; area[c-'a']++; for(int d2=2; d2<4; d2++) anglefill(xy+dxy[d+d2]); return; } } } // mid fill: // .. x. xx // xx becomes xx (and then xx when anglefill is called) void midfill(int xy) { if(kmap[xy] != '.') return; for(int d=0; d<4; d++) { int d0 = d+1; char c = kmap[xy+dxy[d]]; if(c && c != '.' && c == kmap[xy+dxy[d]+dxy[d0]] && kmap[xy+dxy[d0]] == '.') { kmap[xy] = c; area[c-'a']++; for(int d2=0; d2<4; d2++) anglefill(xy+dxy[d2]); for(int d2=0; d2<4; d2++) midfill(xy+dxy[d2]); return; } } } // stupid fill: fill the remaining squares // the color with the largest area is chosen by default, since // this color is probably the one where the cost of losing compactness // is the smallest void stupidfill(int xy) { if(kmap[xy] != '.') return; char choi[8]; int nchoi = 0, areav = 0; /* int ds[4] = {0,1,2,3}; random_shuffle(ds, ds+4); */ for(int d=0; d<4; d++) { char c = kmap[xy+dxy[d]]; if(c && c != '.') { int q = area[c-'a']; if(q > areav) areav = q, nchoi = 0; if(q == areav) choi[nchoi++] = c; } } if(!nchoi) return; char c = nchoi == 1 ? choi[0] : choi[rand() % nchoi]; kmap[xy] = c; area[c-'a']++; for(int d1=0; d1<4; d1++) anglefill(xy+dxy[d1]); for(int d1=0; d1<4; d1++) midfill(xy+dxy[d1]); } // THIRD PHASE: reassign squares between pairs to improve the overall value // first method: just try to switch to another adjacent color, // while making sure that the neighbors of our color remains (locally) connected; // keep if the score improves. Assumes cursc = getscore() bool tryswitch(int xy) { if(cetype[xy] != 2) return false; char c = kmap[xy]; bool which[9]; for(int d=0; d<8; d++) { int xy0 = xy+dxy8[d]; which[d] = kmap[xy0] == c; } which[8] = which[0]; int segs = 0; for(int d=0; d<8; d++) if(which[d] && !which[d+1]) segs++; if(segs != 1) return false; int dirs[4]; for(int u=0; u<4; u++) dirs[u] = u; random_shuffle(dirs, dirs+4); for(int u=0; u<4; u++) { int d = dirs[u]; char c1 = kmap[xy+dxy[d]]; if(!c1) continue; if(c1 == c) continue; swtch(xy, c1); double newsc = compscore(); if(newsc >= cursc) { bool better = newsc > cursc; cursc = newsc; return better; } else { swtch(xy, c); } } return false; } // Second method: find an edge between two colors, and switch one of them // push it down. Rough idea: // xaaaaaaaaaaaabbbbbx xaaaaaaaaaaaabbbbbx // xcccccccccccccccccx => xaaaaaaaaaaaabbbbbx // xcccccccccccccccccx => xcccccccccccccccccx // Has two modes. tsApprox checks that the remaining c's are locally connected, // while tsFull uses vercon to fully verify connectivity. enum tsmode { tsApprox, tsFull }; bool tryswitch2(int xy, tsmode t) { if(cetype[xy] != 2) return false; int dirs[4]; for(int u=0; u<4; u++) dirs[u] = u; random_shuffle(dirs, dirs+4); char c = kmap[xy]; for(int u=0; u<4; u++) { int d = dirs[u]; int bxy = dxy[d]; if(kmap[xy+bxy] == c) continue; if(t == tsApprox && kmap[xy-bxy] != c) continue; if(kmap[xy+bxy] == 0) continue; int dnext = (d+1); int sxy = dxy[dnext]; if(t == tsApprox && kmap[xy-sxy] == c && kmap[xy-sxy-bxy] != c) continue; if(kmap[xy-sxy] == c && kmap[xy-sxy+bxy] != c) continue; int nxy = xy+sxy; while(true) { if(kmap[nxy] != c) break; if(cetype[nxy] != 2) break; if(kmap[nxy+bxy] == c) break; if(t == tsApprox && kmap[nxy-bxy] != c) break; nxy += sxy; } if(nxy == xy+sxy) continue; if(t == tsApprox && kmap[nxy] == c && kmap[nxy-bxy] != c) continue; for(int oxy = xy; oxy != nxy; oxy += sxy) swtch(oxy, kmap[oxy+bxy]); double newsc = compscore(); if(newsc >= cursc && (t == tsApprox || (newsc > cursc && vercon()))) { /* if(!vercon()) { printf("connectivity lost:\n [%s]\n", allgroups); debugshot(); for(int oxy = xy; oxy != nxy; oxy += sxy) swtch(oxy, c); for(int oxy = xy; oxy != nxy; oxy += sxy) cetype[oxy] = 3; cetype[xy] = 4; debugshot(); exit(1); } */ // printf("switched2: %d: %lf -> %lf\n", (nxy-xy) / sxy, cursc, newsc); // debugshot(); bool better = newsc > cursc; cursc = newsc; return better; } for(int oxy = xy; oxy != nxy; oxy += sxy) swtch(oxy, c); } return false; } // call one of the methods (tryswitch, tryswitch2 tsApprox, and tryswitch2 tsFull) // for all squares in a random order vector freespots; bool tryswitchall(int id) { bool stop = false; random_shuffle(freespots.begin(), freespots.end()); for(auto p: freespots) switch(id) { case 1: if(tryswitch(p)) stop = true; break; case 2: if(tryswitch2(p, tsApprox)) stop = true; break; case 3: if(tryswitch2(p, tsFull)) stop = true; break; /* case 4: if(tryswitch3(p)) stop = true; break; */ } return stop; } // ALTERNATIVE APPROACHES //------------------------ // bad fill: an alternative to midfill/stupidfill // find the color of the worst current quality, and fill all the squares // adjacent to this color with it (might be called several times) // idea: it is better to worsen just the worst color than many colors pair quality[20]; void calcquality() { FOR(k,0,K) quality[k].first = area[k] / pow(perim[k], 2.), quality[k].second = k; sort(quality, quality+K); } bool badfill() { calcap(); calcquality(); int pos[20]; int dots = 0; FOR(k,0,K) pos[k] = 0; FOR(y,1,Y+1) FOR(x,1,X+1) { int xy = XY(x, y); if(kmap[xy] == '.') { dots++; FOR(d,0,4) if(kmap[xy+dxy[d]] && kmap[xy+dxy[d]] != '.') pos[kmap[xy+dxy[d]]-'a'] = xy; } } if(!dots) return false; FOR(ki,0,K) { int k = quality[ki].second; if(pos[k]) { // printf("floodfill %c at %d (%d dots)\n", 'a'+k, pos[k], dots); // debugshot(); floodfill(pos[k], 'a'+k); // printf("result:\n"); // debugshot(); // exit(1); return true; } } } // alternatively to useHungarian, instead of using the Hungarian method // we take the currently best solution, take two or three adjacent colors // (with preference for ones with worse quality) and remove them, and possibly // switch their assignments void reuseBest() { if(K == 1) { excthrown = true; return; } int adj[32]; FOR(k,0,K) val[k] = 0, gotit[k] = true, area[k] = 0, perim[k] = 0, paths[k].clear(), adj[k] = 0; ngotit = K; val[31] = -1000000000; FOR(xy,0,MAXBOARD2) kmap[xy] = bestmap[xy]; FOR(xy,0,MAXBOARD2) if(kmap[xy]) { char c = kmap[xy]; int id = c - 'a'; area[id]++; paths[id].push_back(xy); costmap[xy] = CROSSCOST + STEPCOST; if(cetype[xy] != 2) { costmap[xy] += INF; if(cetype[xy] == 1) { hungarian::asg[id] = cid[xy]; } /* if(cetype[xy] == 0) { printf("%d = %d\n", id, cid[xy]); } */ } FOR(d,0,4) { char c1 = kmap[xy + dxy[d]]; if(c1 && c1 != c) perim[id]++, adj[id] |= (1<<(c1-'a')); } } calcquality(); int kpos = rand() % min(K, 5); int ka = quality[kpos].second; int bc = rand() % bitc(adj[ka]); int kb; FOR(k,0,K) if((adj[ka] >> k)&1) { if(!bc) kb = k; bc--; } // printf("last best:\n"); debugshot(); removepath(ka); removepath(kb); if(rand() % 100 < 50) swap(hungarian::asg[ka], hungarian::asg[kb]); if(rand() % 100 < 50) { int adjk = adj[ka] &~ (1<> k)&1) { if(!bc) kc = k; bc--; } removepath(kc); swap(hungarian::asg[ka], hungarian::asg[kc]); } // printf("ka=%c kb=%c\n", 'a'+ka, 'a'+kb); // printf("after removal:\n"); debugshot(); } // MAIN METHODS //-------------- // we call this function repetitively, and return the best one // some randomness is used so that returns of various calls are different void findSolution() { // prepare the variables FOR(xy,0,MAXBOARD2) costmap[xy] = INF, kmap[xy] = 0; FOR(y,1,Y+1) FOR(x,1,X+1) { int xy = XY(x,y); kmap[xy] = '.', cetype[xy] = 2, costmap[xy] = STEPCOST; } FOR(u,0,2) FOR(k,0,K) cetype[pxy[u][k]] = u, cid[pxy[u][k]] = k, costmap[pxy[u][k]] = INF+STEPCOST; hungarian::items = hungarian::bidders = K; // phase I // we normally use Hungarian, but we can use reuseBest() // if half the time has passed and we already have a solution if(bestscore > 0 && curtime > 1000000 && rand() % 100 < 25) reuseBest(); else useHungarian(); if(excthrown) return; int removals = 0; // connect paths, or remove old ones if impossible while(ngotit < K) { int best = 31; { FOR(k0,0,K) if(!gotit[k0] && val[k0] > val[best]) best = k0; vector whichbest; FOR(k0,0,K) if(!gotit[k0] && val[k0] == val[best]) whichbest.push_back(k0); best = whichbest[rand() % Size(whichbest)]; } int k0 = best; int k1 = hungarian::asg[k0]; // printf("[%d-%d] %d,%d -> %d,%d <%d>\n", k0, k1, py[0][k0], px[0][k0], py[1][k1], px[1][k1], val[k0]); char c= 'a' + k0; int xy0 = pxy[0][k0]; int xy1 = pxy[1][k1]; kmap[xy0] = '.'; costmap[xy0] -= INF; kmap[xy1] = '.'; costmap[xy1] -= INF; pathfind(xy0,xy1,paths[k0]); costmap[xy0] += INF; costmap[xy1] += INF; if(excthrown) return; pathsremoved.clear(); placepath(k0); if(Size(pathsremoved)) { removals++; if(removals < 32) continue; if(curtime < 250000) { excthrown = true; return; } if(removals > 320 && bestscore > 0) { excthrown = true; return; } if(removals > 1000) { excthrown = true; return; } int r = rand() % 6; if(r == 0) { removepath(k0); int ipath = pathsremoved[rand() % Size(pathsremoved)]; swap(hungarian::asg[k0], hungarian::asg[ipath]); } if(r == 1) { vector stillin; for(int c=0; c stillout; for(int c=0; c X || GETY(xy) == 0 || GETY(xy) > Y) kmap[xy] = 1; if(typ == 1) FOR(u,0,2) FOR(k,0,K) { again: int py = 1 + rand() % Y, px= 1 + rand() % X; int p = XY(px, py); if(kmap[p]) goto again; kmap[p] = 1; pxy[u][k] = p; } if(typ == 2) FOR(u,0,2) FOR(k,0,K) { again2: int py = 1 + rand() % Y, px= 1 + rand() % X; int p = XY(px, py); if(u == 1) p = pxy[0][k] + XY(rand() % 3 - 1, rand() % 3 - 1); if(kmap[p]) goto again2; kmap[p] = 1; pxy[u][k] = p; } if(typ == 3) FOR(u,0,2) FOR(k,0,K) { again3: int py = Y*(1+2*u)/5 + rand() % (Y/5), px=X*(1+2*u)/5 + rand() % (X/5); int p = XY(px, py); if(kmap[p]) goto again3; kmap[p] = 1; pxy[u][k] = p; } } else { FOR(u,0,2) FOR(k,0,K) { int py = getNum()+1; int px = getNum()+1; pxy[u][k] = XY(px, py); } } // main findSolution() loop ll t= getVa(); bestscore = -1; double avgscore = 0; int excs = 0; while(true) { curtime = getVa() - t; if(curtime > (tryindex >= 100 ? 1900000 : 1800000) && bestscore > 0) break; // try { tryindex++; excthrown = false; findSolution(); if(excthrown) {excs++; continue; } double sc = getscore(); avgscore += sc; if(sc > bestscore) { bestscore = sc; FOR(xy,0,MAXBOARD2) bestmap[xy] = kmap[xy]; } // printf("res = %lf\n", getscore()); // } // catch(failed f) { } } #ifdef LOCAL FOR(xy,0,MAXBOARD2) kmap[xy] = bestmap[xy]; getscore(); printf("bestval = %lf\n", bestscore); printf("avg val = %lf\n", avgscore / (tryindex-excs)); printf("tryindex = %d (%d)\n", tryindex, excs); debugshot(); #else FOR(y,1,Y+1) printf("%s\n", bestmap+y*MAXBOARD+1); #endif } #define P 1000000007 int main() { if(!MANYTESTS) Tests = 1; else Tests = getNum(); for(cnum=1; cnum<=Tests; cnum++) solveCase(); // finish return 0; } void debugshot() { FOR(y,1,Y+1) { FOR(x,1,X+1) { int xy = XY(x,y); int t = cetype[xy]; if(t == 0) ansicol16(9); if(t == 1) ansicol16(12); if(t == 3) ansicol16(10); if(t == 4) ansicol16(13); printf("%c", kmap[xy]); if(t != 2) ansiclear(); } int k = y-1; if(k < K && perim[k]) { printf(" "); printf("%c: area=%4d peri=%4d %lf", 'a'+k, area[k], perim[k], 16*area[k] / pow(perim[k], 2)); } printf("\n"); } }