ens-ulm-1-2015

commit 4ceebfb4c656ce789a62068987af199c69a1a7ce
parent d550a3d04cb26beaaf3dd7602ed3692f8cef3990
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Thu, 12 Mar 2015 19:25:52 +0100

continue

Diffstat:
a3nm/server.cpp
 | 
44
+++++++++++++++++++++++++++++++++++++++++++-

1 file changed, 43 insertions(+), 1 deletion(-)
diff --git a/a3nm/server.cpp b/a3nm/server.cpp
@@ -8,13 +8,14 @@ using namespace std;
 #define MAXN 1002
 
 typedef pair<int,int> pii;
+typedef pair<int,pii> piii;
 
 int main() {
   int R, S, U, P, M;
   vector<pii> serv;
   char grid[MAXN][MAXN]; // row, col
   int capa[MAXN];
-  int gcapa[MAXN][MAXN];
+  int gcapa[MAXN][MAXN]; // row, group
   int fposr[MAXN], fposc[MAXN], fgroup[MAXN];
 
   scanf("%d", &R);
@@ -46,6 +47,47 @@ int main() {
   }
 
   for (int i = 0; i < M; i++) {
+    // place server i
+    // choose the group with lowest guaranteed
+    int guar[MAXN];
+    for (int j = 0; j < P; j++)
+      guar[j] = capa[j];
+    for (int j = 0; j < R; j++)
+      for (int k = 0; k < P; k++)
+        guar[k] = min(guar[k], capa[k] - gcapa[j][k]);
+    int mguar = guar[0], idx = 0;
+    for (int j = 0; j < P; j++)
+      if (guar[j] < mguar) {
+        mguar = guar[j];
+        idx = j;
+      }
+    // idx is the group
+    // choose where to place server
+    vector<pii> v;
+    int where = -1;
+    for (int j = 0; j < R; j++)
+      v.push_back(make_pair<int, int>(gcapa[j][idx], j));
+    sort(v.begin(), v.end());
+    for (int j = 0; j < R; j++) {
+      // try to place in row
+      int row = v[j].second;
+      int contig = 0;
+      for (int k = 0; k < S; k++) {
+        if (!grid[row][k])
+          contig++;
+        else
+          contig = 0;
+        if (contig == serv[i].second) {
+          // ok, can place
+          break;
+        }
+      }
+      if (contig == serv[i].second) {
+        // do place
+        where = k - (serv[i].second - 1);
+        break;
+      }
+    }
     // place serv[i]
   }