388.cpp (3016B)
1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4 5 using namespace std; 6 7 // generous bound on all possible inputs and sizes 8 #define MAXN 1002 9 10 struct Server { 11 int id, z, c; 12 Server(int id = 0, int z = 0, int c = 0) : id(id), z(z), c(c) {} 13 // sort servers by decreasing c/z then decreasing z 14 bool operator< (const Server &s) const { 15 // a/b < c/d iff da < bc and (e, f) < (g, h) with f,h < N iff eN+f < gN+h 16 return z*s.c*MAXN + s.z < s.z*c*MAXN + z; 17 } 18 }; 19 20 // declaring those globally means we don't have to initialize them 21 int R, S, U, P, M; 22 vector<Server> serv; 23 char grid[MAXN][MAXN]; // filled grid cells, indexed by row, col 24 int capa[MAXN]; // capa[g]: total capacity allocated to group g 25 int gcapa[MAXN][MAXN]; // gcapa[r][g]: total capacity for group g in row r 26 vector<pair<int, pair<int, int> > > out; // group, row, col 27 28 int main(int argc, char **argv) { 29 scanf("%d%d%d%d%d", &R, &S, &U, &P, &M); 30 for (int i = 0; i < U; i++) { 31 int r, s; 32 scanf("%d%d", &r, &s); 33 grid[r][s] = 1; // grid cell is occupied 34 } 35 for (int i = 0; i < M; i++) { 36 int z, c; 37 scanf("%d%d", &z, &c); 38 serv.push_back(Server(i, z, c)); 39 out.push_back(make_pair(-1, make_pair(-1, -1))); // server is unused 40 } 41 42 sort(serv.begin(), serv.end()); 43 44 for (int s = 0; s < M; s++) { 45 // place server s 46 int guar[MAXN]; // guar[g]: guaranteed capa for group g 47 for (int g = 0; g < P; g++) 48 guar[g] = capa[g]; 49 for (int r = 0; r < R; r++) 50 for (int g = 0; g < P; g++) 51 guar[g] = min(guar[g], capa[g] - gcapa[r][g]); // capa if killing row r 52 int mguar = guar[0], mg = 0; // min and argmin of guar over all groups 53 for (int g = 0; g < P; g++) 54 if (guar[g] < mguar) { 55 mguar = guar[g]; 56 mg = g; 57 } 58 // mg is the group with lowest guar, assign s to mg if we can place it 59 vector<pair<int, int> > rows; 60 for (int r = 0; r < R; r++) 61 rows.push_back(make_pair<int, int>(gcapa[r][mg], r)); 62 sort(rows.begin(), rows.end()); // sort rows by inc capa for group mg 63 int fr = -1, fc = -1; // row and col to place s 64 for (int rr = 0; rr < R; rr++) { 65 int contig = 0; // count contiguous free cells 66 fr = rows[rr].second; 67 for (int c = 0; c < S; c++) { 68 if (!grid[fr][c]) 69 contig++; 70 else 71 contig = 0; 72 if (contig == serv[s].z) { 73 fc = c - (serv[s].z - 1); // we can place s at (fr, fc) 74 rr = R; // break out of both loops 75 break; 76 } 77 } 78 } 79 if (fc >= 0) { 80 // assign s to mg and place it at (fr, fc) 81 capa[mg] += serv[s].c; 82 gcapa[fr][mg] += serv[s].c; 83 for (int d = 0; d < serv[s].z; d++) 84 grid[fr][fc+d] = 1; // squares occupied by s 85 out[serv[s].id] = make_pair(mg, make_pair(fr, fc)); 86 } 87 } 88 89 for (int i= 0 ; i < M; i++) 90 if (out[i].first >= 0) 91 printf("%d %d %d\n", out[i].first, 92 out[i].second.first, out[i].second.second); 93 else 94 printf("x\n"); 95 96 return 0; 97 } 98