final.cpp (7227B)
1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <map> 5 #include <time.h> 6 7 // g++ -o 400 -O2 470_gives_400.cpp 8 // ./400 470 < ../dc.in |tail -1000 | grep -A999999 WOOT | sed 1d > my400 9 10 using namespace std; 11 12 #define MAXN 1002 13 14 typedef pair<int,int> pii; 15 typedef pair<int,pii> piii; 16 17 struct Server{ 18 int id, z, c; 19 Server(int id=0, int z=0, int c=0) : id(id), z(z), c(c) {} 20 bool operator< (const Server &s) const{ 21 if (z*s.c == s.z*c) return z > s.z; 22 return z*s.c < s.z*c; 23 } 24 }; 25 26 struct comp{ 27 bool operator() (const Server &a, const Server &b){ 28 if (a.z == b.z) 29 return a.c > b.c; 30 return a.z > b.z; 31 } 32 }; 33 34 int R, S, U, P, M; 35 vector<Server> serv; 36 Server oserv[MAXN]; 37 char grid[MAXN][MAXN]; // row, col 38 int capa[MAXN]; 39 int space[MAXN]; // free space 40 int gcapa[MAXN][MAXN]; // row, group 41 int fposr[MAXN], fposc[MAXN], fgroup[MAXN]; 42 43 44 int swap(int rsl, int rsh) { 45 int tmp; 46 int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh]; 47 tmp = fposr[rsh]; 48 fposr[rsh] = fposr[rsl]; 49 fposr[rsl] = tmp; 50 tmp = fposc[rsh]; 51 fposc[rsh] = fposc[rsl]; 52 fposc[rsl] = tmp; 53 tmp = fgroup[rsh]; 54 fgroup[rsh] = fgroup[rsl]; 55 fgroup[rsl] = tmp; 56 gcapa[rh][gh] += oserv[rsl].c - oserv[rsh].c; 57 gcapa[rl][gl] += oserv[rsh].c - oserv[rsl].c; 58 capa[gh] += oserv[rsl].c - oserv[rsh].c; 59 capa[gl] += oserv[rsh].c - oserv[rsl].c; 60 } 61 62 63 int gapas(int fguar[MAXN]) { 64 for (int j = 0; j < P; j++) 65 fguar[j] = capa[j]; 66 for (int j = 0; j < R; j++) 67 for (int k = 0; k < P; k++) 68 fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]); 69 int mfguar = fguar[0]; 70 int g = 0; 71 for (int j = 0; j < P; j++) 72 if (fguar[j] < mfguar) { 73 mfguar = fguar[j]; 74 g = j; 75 } 76 return g; 77 } 78 79 80 81 int main(int argc, char **argv) { 82 scanf("%d", &R); 83 scanf("%d", &S); 84 scanf("%d", &U); 85 scanf("%d", &P); 86 scanf("%d", &M); 87 srand(45); 88 for (int i = 0; i < R; i++) 89 space[i] = S; 90 for (int i = 0; i < U; i++) { 91 int r, s; 92 scanf("%d", &r); 93 scanf("%d", &s); 94 grid[r][s] = 1; 95 space[r] -= 1; 96 } 97 for (int i = 0; i < M; i++) { 98 int z, c; 99 scanf("%d", &z); 100 scanf("%d", &c); 101 serv.push_back(Server(i, z, c)); 102 oserv[i] = Server(i, z, c); 103 } 104 105 sort(serv.begin(), serv.end()); 106 107 // now keep only the servers we will use 108 int free = R * S - U; 109 int besttcapa = 0; 110 111 int i; 112 for (i = 0; i < M; i++) { 113 free -= serv[i].c; // should be .z, but???! 114 if (free >= 0) 115 besttcapa += serv[i].c; 116 if (free <= 0) 117 break; 118 } 119 120 // for i in `seq 500`; do echo -n "$i "; ./a.out $i < ../dc.in | grep FINAL | cut -d ' ' -f2 ; done | sort -k2,2n 121 // USE 470 122 sort(serv.begin(), serv.begin() + i + atoi(argv[1]), comp()); 123 124 int ftcapa = 0; 125 for (int i = 0; i < M; i++) { 126 fposr[i] = fposc[i] = fgroup[i] = -1; 127 } 128 129 for (int i = 0; i < M; i++) { 130 // place server i 131 printf("i want to place server %d id %d c %d z %d, c/z %f\n", i, serv[i].id, serv[i].c, serv[i].z, 1. * serv[i].c/serv[i].z); 132 // choose the group with lowest guaranteed 133 int guar[MAXN]; 134 for (int j = 0; j < P; j++) 135 guar[j] = capa[j]; 136 for (int j = 0; j < R; j++) 137 for (int k = 0; k < P; k++) 138 guar[k] = min(guar[k], capa[k] - gcapa[j][k]); 139 int mguar = guar[0]; 140 int idx = 0; 141 for (int j = 0; j < P; j++) 142 if (guar[j] < mguar) { 143 mguar = guar[j]; 144 idx = j; 145 } 146 // idx is the group 147 // choose where to place server 148 vector<pii> v; 149 int wherecol = -1, whererow = -1; 150 for (int j = 0; j < R; j++) { 151 printf("gcapa of row is %d and space is %d\n", gcapa[j][idx], space[j]); 152 v.push_back(make_pair<int, int>(MAXN * gcapa[j][idx] + (MAXN-1) - space[j], j)); 153 } 154 sort(v.begin(), v.end()); 155 for (int j = 0; j < R; j++) { 156 // try to place in row 157 int row = v[j].second; 158 int contig = 0; 159 int k; 160 for (k = 0; k < S; k++) { 161 if (!grid[row][k]) 162 contig++; 163 else 164 contig = 0; 165 if (contig == serv[i].z) { 166 // ok, can place 167 break; 168 } 169 } 170 if (contig == serv[i].z) { 171 // do place 172 wherecol = k - (serv[i].z - 1); 173 whererow = row; 174 break; 175 } 176 } 177 if (wherecol >= 0 && whererow >= 0) { 178 // yeah, we can place it! update 179 capa[idx] += serv[i].c; 180 gcapa[whererow][idx] += serv[i].c; 181 for (int k = 0; k < serv[i].z; k++) 182 grid[whererow][wherecol+k] = 2; 183 fposr[serv[i].id] = whererow; 184 fposc[serv[i].id] = wherecol; 185 fgroup[serv[i].id] = idx; 186 space[whererow] -= serv[i].z; 187 ftcapa += serv[i].c; 188 } else { 189 printf("CANNOT PLACE!!\n"); 190 } 191 } 192 193 int MAXT = 1000000000; 194 for (int nsw = 0; nsw < MAXT; nsw++) { 195 int rsl = rand() % M; 196 int rsh = rand() % M; 197 int rsl2 = rand() % M; 198 int rsh2 = rand() % M; 199 if (rsl == rsh || rsl == rsl2 || rsl == rsh2 || rsh == rsl2 || rsh == rsh2 || rsl2 == rsh2) 200 continue; 201 if (oserv[rsl].z != oserv[rsh].z) 202 continue; 203 if (oserv[rsl2].z != oserv[rsh2].z) 204 continue; 205 if (fgroup[rsl] < 0 || fgroup[rsh] < 0) 206 continue; 207 if (fgroup[rsl2] < 0 || fgroup[rsh2] < 0) 208 continue; 209 int thefguar[MAXN]; 210 int wg = gapas(thefguar); 211 int oldcapa = thefguar[wg]; 212 213 printf("GCAPA %d\n", oldcapa); 214 215 // try swap 216 // int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh]; 217 // printf("swap servers %d %d\n", rsl, rsh); 218 // printf("swap rows %d %d\n", rl, rh); 219 // printf("capas on rows are %d %d\n", gcapa[rl][gl], gcapa[rh][gh]); 220 // printf("their groups are: %d %d\n", fgroup[rsl], fgroup[rsh]); 221 // printf("their capas are: %d %d\n", oserv[rsl].c, oserv[rsh].c); 222 // printf("their sizes are: %d %d\n", oserv[rsl].z, oserv[rsh].z); 223 224 // do swap 225 int tmp; 226 swap(rsl, rsh); 227 swap(rsl2, rsh2); 228 229 int nwg = gapas(thefguar); 230 int newcapa = thefguar[nwg]; 231 232 printf("GCAPA is now: %d\n", newcapa); 233 234 if (newcapa >= oldcapa) { 235 if (newcapa > oldcapa) { 236 printf("WOOT\n"); 237 for (int i= 0 ; i < M; i++) { 238 if (fposr[i] >= 0) 239 printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]); 240 else 241 printf("x\n"); 242 } 243 exit(0); 244 } 245 printf("KEEEEEP\n"); 246 continue; 247 } 248 249 // rollback 250 swap(rsh, rsl); 251 swap(rsh2, rsl2); 252 } 253 254 int fguar[MAXN]; 255 for (int j = 0; j < P; j++) 256 fguar[j] = capa[j]; 257 for (int j = 0; j < R; j++) 258 for (int k = 0; k < P; k++) 259 fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]); 260 int mfguar = fguar[0]; 261 int idx = 0; 262 for (int j = 0; j < P; j++) 263 if (fguar[j] < mfguar) { 264 mfguar = fguar[j]; 265 idx = j; 266 } 267 268 printf("best %d placed %d\n", besttcapa, ftcapa); 269 for (int i = 0; i < P; i++) 270 printf("guar for %d: %d\n", i, fguar[i]); 271 printf("FINAL: %d\n", mfguar); 272 273 for (int i = 0; i < R; i++) { 274 for (int j = 0; j < S; j++) 275 putchar(grid[i][j] == 1? 'X' : (grid[i][j] == 2 ? 'O' : ' ')); 276 putchar('\n'); 277 } 278 279 printf("CUT\n"); 280 281 // display sol 282 for (int i= 0 ; i < M; i++) { 283 if (fposr[i] >= 0) 284 printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]); 285 else 286 printf("x\n"); 287 } 288 289 return 0; 290 } 291