470_gives_399.cpp (4516B)
1 #include <vector> 2 #include <cstdio> 3 #include <algorithm> 4 #include <map> 5 6 // Compile WITHOUT OPTIMS!! 7 8 using namespace std; 9 10 #define MAXN 1002 11 12 typedef pair<int,int> pii; 13 typedef pair<int,pii> piii; 14 15 struct Server{ 16 int id, z, c; 17 Server(int id=0, int z=0, int c=0) : id(id), z(z), c(c) {} 18 bool operator< (const Server &s) const{ 19 if (z*s.c == s.z*c) return z > s.z; 20 return z*s.c < s.z*c; 21 } 22 }; 23 24 struct comp{ 25 bool operator() (const Server &a, const Server &b){ 26 if (a.z == b.z) 27 return a.c > b.c; 28 return a.z > b.z; 29 } 30 }; 31 32 int main(int argc, char **argv) { 33 int R, S, U, P, M; 34 vector<Server> serv; 35 char grid[MAXN][MAXN]; // row, col 36 int capa[MAXN]; 37 int space[MAXN]; // free space 38 int gcapa[MAXN][MAXN]; // row, group 39 int fposr[MAXN], fposc[MAXN], fgroup[MAXN]; 40 41 scanf("%d", &R); 42 scanf("%d", &S); 43 scanf("%d", &U); 44 scanf("%d", &P); 45 scanf("%d", &M); 46 for (int i = 0; i < R; i++) 47 space[i] = S; 48 for (int i = 0; i < U; i++) { 49 int r, s; 50 scanf("%d", &r); 51 scanf("%d", &s); 52 grid[r][s] = 1; 53 space[r] -= 1; 54 } 55 for (int i = 0; i < M; i++) { 56 int z, c; 57 scanf("%d", &z); 58 scanf("%d", &c); 59 serv.push_back(Server(i, z, c)); 60 } 61 62 sort(serv.begin(), serv.end()); 63 64 // now keep only the servers we will use 65 int free = R * S - U; 66 int besttcapa = 0; 67 68 int i; 69 for (i = 0; i < M; i++) { 70 free -= serv[i].c; // should be .z, but???! 71 if (free >= 0) 72 besttcapa += serv[i].c; 73 if (free <= 0) 74 break; 75 } 76 77 // for i in `seq 500`; do echo -n "$i "; ./a.out $i < ../dc.in | grep FINAL | cut -d ' ' -f2 ; done | sort -k2,2n 78 // USE 470 79 sort(serv.begin(), serv.begin() + i + atoi(argv[1]), comp()); 80 81 int ftcapa = 0; 82 for (int i = 0; i < M; i++) { 83 fposr[i] = fposc[i] = fgroup[i] = -1; 84 } 85 86 for (int i = 0; i < M; i++) { 87 // place server i 88 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); 89 // choose the group with lowest guaranteed 90 int guar[MAXN]; 91 for (int j = 0; j < P; j++) 92 guar[j] = capa[j]; 93 for (int j = 0; j < R; j++) 94 for (int k = 0; k < P; k++) 95 guar[k] = min(guar[k], capa[k] - gcapa[j][k]); 96 int mguar = guar[0]; 97 int idx = 0; 98 for (int j = 0; j < P; j++) 99 if (guar[j] < mguar) { 100 mguar = guar[j]; 101 idx = j; 102 } 103 // idx is the group 104 // choose where to place server 105 vector<pii> v; 106 int wherecol = -1, whererow = -1; 107 for (int j = 0; j < R; j++) { 108 printf("gcapa of row is %d and space is %d\n", gcapa[j][idx], space[j]); 109 v.push_back(make_pair<int, int>(MAXN * gcapa[j][idx] + (MAXN-1) - space[j], j)); 110 } 111 sort(v.begin(), v.end()); 112 for (int j = 0; j < R; j++) { 113 // try to place in row 114 int row = v[j].second; 115 int contig = 0; 116 int k; 117 for (k = 0; k < S; k++) { 118 if (!grid[row][k]) 119 contig++; 120 else 121 contig = 0; 122 if (contig == serv[i].z) { 123 // ok, can place 124 break; 125 } 126 } 127 if (contig == serv[i].z) { 128 // do place 129 wherecol = k - (serv[i].z - 1); 130 whererow = row; 131 break; 132 } 133 } 134 if (wherecol >= 0 && whererow >= 0) { 135 // yeah, we can place it! update 136 capa[idx] += serv[i].c; 137 gcapa[whererow][idx] += serv[i].c; 138 for (int k = 0; k < serv[i].z; k++) 139 grid[whererow][wherecol+k] = 2; 140 fposr[serv[i].id] = whererow; 141 fposc[serv[i].id] = wherecol; 142 fgroup[serv[i].id] = idx; 143 space[whererow] -= serv[i].z; 144 ftcapa += serv[i].c; 145 } else { 146 printf("CANNOT PLACE!!\n"); 147 } 148 } 149 150 151 int fguar[MAXN]; 152 for (int j = 0; j < P; j++) 153 fguar[j] = capa[j]; 154 for (int j = 0; j < R; j++) 155 for (int k = 0; k < P; k++) 156 fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]); 157 int mfguar = fguar[0]; 158 for (int j = 0; j < P; j++) 159 if (fguar[j] < mfguar) { 160 mfguar = fguar[j]; 161 } 162 163 printf("best %d placed %d\n", besttcapa, ftcapa); 164 for (int i = 0; i < P; i++) 165 printf("guar for %d: %d\n", i, fguar[i]); 166 printf("FINAL: %d\n", mfguar); 167 168 for (int i = 0; i < R; i++) { 169 for (int j = 0; j < S; j++) 170 putchar(grid[i][j] == 1? 'X' : (grid[i][j] == 2 ? 'O' : ' ')); 171 putchar('\n'); 172 } 173 174 printf("CUT\n"); 175 176 // display sol 177 for (int i= 0 ; i < M; i++) { 178 if (fposr[i] >= 0) 179 printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]); 180 else 181 printf("x\n"); 182 } 183 184 return 0; 185 } 186