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