useless.c (3126B)
1 2 int did = 1; 3 while (did) { 4 did = 0; 5 int fguar[MAXN]; 6 for (int j = 0; j < P; j++) 7 fguar[j] = capa[j]; 8 for (int j = 0; j < R; j++) 9 for (int k = 0; k < P; k++) 10 fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]); 11 int mfguar = fguar[0]; 12 int g = 0; 13 for (int j = 0; j < P; j++) 14 if (fguar[j] < mfguar) { 15 mfguar = fguar[j]; 16 g = j; 17 } 18 printf("guar is %d, optimize worst group: %d\n", mfguar, g); 19 // optimize g 20 vector<pii> vv; 21 for (int r = 0; r < R; r++) 22 vv.push_back(make_pair(gcapa[r][g], r)); 23 sort(vv.begin(), vv.end()); 24 for (int rh = R - 1; rh >= 0; rh--) { 25 if (vv[rh].first < vv[R-1].first) 26 break; 27 for (int rl = 0; rl < rh; rl++) { 28 //printf("swap in rl %d rh %d\n", rl, rh); 29 vector<int> sl, sh; 30 for (int s = 0; s < M; s++) { 31 if (fgroup[s] != g) 32 continue; 33 //printf("aoeu servera %d is in %d\n", s, fposr[s]); 34 if (fposr[s] == vv[rh].second) 35 sh.push_back(s); 36 if (fposr[s] == vv[rl].second) 37 sl.push_back(s); 38 } 39 int tcapal = 0; 40 for (unsigned int ssl = 0; ssl < sl.size(); ssl++) 41 tcapal += oserv[sl[ssl]].c; 42 printf("calculated capa of l as %d and should be %d\n", tcapal, gcapa[vv[rl].second][g]); 43 //printf("aoeu i have %d %d servers\n", sl.size(), sh.size()); 44 for (unsigned int ssl = 0; ssl < sl.size(); ssl++) { 45 for (unsigned int ssh = 0; ssh < sh.size(); ssh++) { 46 int rsh = sh[ssh]; 47 int rsl = sl[ssl]; 48 //printf("aoeu soeu wap consider rsl %d rsh %d\n", rsl, rsh); 49 // try to swap rsl and rsh 50 if (oserv[rsl].z != oserv[rsh].z) 51 continue; 52 if (oserv[rsh].c <= oserv[rsl].c) 53 continue; 54 if (gcapa[vv[rl].second][g] + oserv[rsh].c - oserv[rsl].c >= gcapa[vv[rh].second][g]) 55 continue; 56 // can swap 57 did = 1; 58 printf("swap servers %d %d\n", rsl, rsh); 59 printf("swap rows %d %d\n", vv[rl].second, vv[rh].second); 60 printf("capas on rows are %d %d\n", gcapa[rl][g], gcapa[rh][g]); 61 printf("capas on rows will be %d %d\n", gcapa[rl][g] + oserv[rsh].c - oserv[rsh].c, 62 gcapa[rh][g] + oserv[rsl].c - oserv[rsh].c); 63 printf("their groups are: %d %d\n", fgroup[rsl], fgroup[rsh]); 64 printf("their capas are: %d %d\n", oserv[rsl].c, oserv[rsh].c); 65 printf("their sizes are: %d %d\n", oserv[rsl].z, oserv[rsh].z); 66 // do swap 67 int tmp; 68 tmp = fposr[rsh]; 69 fposr[rsh] = fposr[rsl]; 70 fposr[rsl] = tmp; 71 tmp = fposc[rsh]; 72 fposc[rsh] = fposc[rsl]; 73 fposc[rsl] = tmp; 74 gcapa[rh][g] += oserv[rsl].c - oserv[rsh].c; 75 gcapa[rl][g] += oserv[rsh].c - oserv[rsl].c; 76 break; 77 } 78 if (did) 79 break; 80 } 81 if (did) 82 break; 83 } 84 if (did) 85 break; 86 } 87 }