commit da8c293518565c07bafc6146903ada8e32ad3310
parent 1e69944c1dfdf04ae60ad0392c1f16f080e4f369
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 12 Mar 2015 23:10:28 +0100
final
Diffstat:
| a3nm/470_gives_400.cpp | | | 291 | ------------------------------------------------------------------------------ |
| a3nm/final | | | 625 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| a3nm/final.cpp | | | 291 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
3 files changed, 916 insertions(+), 291 deletions(-)
diff --git a/a3nm/470_gives_400.cpp b/a3nm/470_gives_400.cpp
@@ -1,291 +0,0 @@
-#include <vector>
-#include <cstdio>
-#include <algorithm>
-#include <map>
-#include <time.h>
-
-// g++ -o 400 -O2 470_gives_400.cpp
-// ./400 470 < ../dc.in |tail -1000 | grep -A999999 WOOT | sed 1d > my400
-
-using namespace std;
-
-#define MAXN 1002
-
-typedef pair<int,int> pii;
-typedef pair<int,pii> piii;
-
-struct Server{
- int id, z, c;
- Server(int id=0, int z=0, int c=0) : id(id), z(z), c(c) {}
- bool operator< (const Server &s) const{
- if (z*s.c == s.z*c) return z > s.z;
- return z*s.c < s.z*c;
- }
-};
-
-struct comp{
- bool operator() (const Server &a, const Server &b){
- if (a.z == b.z)
- return a.c > b.c;
- return a.z > b.z;
- }
-};
-
-int R, S, U, P, M;
-vector<Server> serv;
-Server oserv[MAXN];
-char grid[MAXN][MAXN]; // row, col
-int capa[MAXN];
-int space[MAXN]; // free space
-int gcapa[MAXN][MAXN]; // row, group
-int fposr[MAXN], fposc[MAXN], fgroup[MAXN];
-
-
-int swap(int rsl, int rsh) {
- int tmp;
- int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh];
- tmp = fposr[rsh];
- fposr[rsh] = fposr[rsl];
- fposr[rsl] = tmp;
- tmp = fposc[rsh];
- fposc[rsh] = fposc[rsl];
- fposc[rsl] = tmp;
- tmp = fgroup[rsh];
- fgroup[rsh] = fgroup[rsl];
- fgroup[rsl] = tmp;
- gcapa[rh][gh] += oserv[rsl].c - oserv[rsh].c;
- gcapa[rl][gl] += oserv[rsh].c - oserv[rsl].c;
- capa[gh] += oserv[rsl].c - oserv[rsh].c;
- capa[gl] += oserv[rsh].c - oserv[rsl].c;
-}
-
-
-int gapas(int fguar[MAXN]) {
- for (int j = 0; j < P; j++)
- fguar[j] = capa[j];
- for (int j = 0; j < R; j++)
- for (int k = 0; k < P; k++)
- fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]);
- int mfguar = fguar[0];
- int g = 0;
- for (int j = 0; j < P; j++)
- if (fguar[j] < mfguar) {
- mfguar = fguar[j];
- g = j;
- }
- return g;
-}
-
-
-
-int main(int argc, char **argv) {
- scanf("%d", &R);
- scanf("%d", &S);
- scanf("%d", &U);
- scanf("%d", &P);
- scanf("%d", &M);
- srand(45);
- for (int i = 0; i < R; i++)
- space[i] = S;
- for (int i = 0; i < U; i++) {
- int r, s;
- scanf("%d", &r);
- scanf("%d", &s);
- grid[r][s] = 1;
- space[r] -= 1;
- }
- for (int i = 0; i < M; i++) {
- int z, c;
- scanf("%d", &z);
- scanf("%d", &c);
- serv.push_back(Server(i, z, c));
- oserv[i] = Server(i, z, c);
- }
-
- sort(serv.begin(), serv.end());
-
- // now keep only the servers we will use
- int free = R * S - U;
- int besttcapa = 0;
-
- int i;
- for (i = 0; i < M; i++) {
- free -= serv[i].c; // should be .z, but???!
- if (free >= 0)
- besttcapa += serv[i].c;
- if (free <= 0)
- break;
- }
-
- // for i in `seq 500`; do echo -n "$i "; ./a.out $i < ../dc.in | grep FINAL | cut -d ' ' -f2 ; done | sort -k2,2n
- // USE 470
- sort(serv.begin(), serv.begin() + i + atoi(argv[1]), comp());
-
- int ftcapa = 0;
- for (int i = 0; i < M; i++) {
- fposr[i] = fposc[i] = fgroup[i] = -1;
- }
-
- for (int i = 0; i < M; i++) {
- // place server i
- 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);
- // 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];
- int 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 wherecol = -1, whererow = -1;
- for (int j = 0; j < R; j++) {
- printf("gcapa of row is %d and space is %d\n", gcapa[j][idx], space[j]);
- v.push_back(make_pair<int, int>(MAXN * gcapa[j][idx] + (MAXN-1) - space[j], 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;
- int k;
- for (k = 0; k < S; k++) {
- if (!grid[row][k])
- contig++;
- else
- contig = 0;
- if (contig == serv[i].z) {
- // ok, can place
- break;
- }
- }
- if (contig == serv[i].z) {
- // do place
- wherecol = k - (serv[i].z - 1);
- whererow = row;
- break;
- }
- }
- if (wherecol >= 0 && whererow >= 0) {
- // yeah, we can place it! update
- capa[idx] += serv[i].c;
- gcapa[whererow][idx] += serv[i].c;
- for (int k = 0; k < serv[i].z; k++)
- grid[whererow][wherecol+k] = 2;
- fposr[serv[i].id] = whererow;
- fposc[serv[i].id] = wherecol;
- fgroup[serv[i].id] = idx;
- space[whererow] -= serv[i].z;
- ftcapa += serv[i].c;
- } else {
- printf("CANNOT PLACE!!\n");
- }
- }
-
- int MAXT = 1000000000;
- for (int nsw = 0; nsw < MAXT; nsw++) {
- int rsl = rand() % M;
- int rsh = rand() % M;
- int rsl2 = rand() % M;
- int rsh2 = rand() % M;
- if (rsl == rsh || rsl == rsl2 || rsl == rsh2 || rsh == rsl2 || rsh == rsh2 || rsl2 == rsh2)
- continue;
- if (oserv[rsl].z != oserv[rsh].z)
- continue;
- if (oserv[rsl2].z != oserv[rsh2].z)
- continue;
- if (fgroup[rsl] < 0 || fgroup[rsh] < 0)
- continue;
- if (fgroup[rsl2] < 0 || fgroup[rsh2] < 0)
- continue;
- int thefguar[MAXN];
- int wg = gapas(thefguar);
- int oldcapa = thefguar[wg];
-
- printf("GCAPA %d\n", oldcapa);
-
- // try swap
- // int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh];
- // printf("swap servers %d %d\n", rsl, rsh);
- // printf("swap rows %d %d\n", rl, rh);
- // printf("capas on rows are %d %d\n", gcapa[rl][gl], gcapa[rh][gh]);
- // printf("their groups are: %d %d\n", fgroup[rsl], fgroup[rsh]);
- // printf("their capas are: %d %d\n", oserv[rsl].c, oserv[rsh].c);
- // printf("their sizes are: %d %d\n", oserv[rsl].z, oserv[rsh].z);
-
- // do swap
- int tmp;
- swap(rsl, rsh);
- swap(rsl2, rsh2);
-
- int nwg = gapas(thefguar);
- int newcapa = thefguar[nwg];
-
- printf("GCAPA is now: %d\n", newcapa);
-
- if (newcapa >= oldcapa) {
- if (newcapa > oldcapa) {
- printf("WOOT\n");
- for (int i= 0 ; i < M; i++) {
- if (fposr[i] >= 0)
- printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]);
- else
- printf("x\n");
- }
- exit(0);
- }
- printf("KEEEEEP\n");
- continue;
- }
-
- // rollback
- swap(rsh, rsl);
- swap(rsh2, rsl2);
- }
-
- int fguar[MAXN];
- for (int j = 0; j < P; j++)
- fguar[j] = capa[j];
- for (int j = 0; j < R; j++)
- for (int k = 0; k < P; k++)
- fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]);
- int mfguar = fguar[0];
- int idx = 0;
- for (int j = 0; j < P; j++)
- if (fguar[j] < mfguar) {
- mfguar = fguar[j];
- idx = j;
- }
-
- printf("best %d placed %d\n", besttcapa, ftcapa);
- for (int i = 0; i < P; i++)
- printf("guar for %d: %d\n", i, fguar[i]);
- printf("FINAL: %d\n", mfguar);
-
- for (int i = 0; i < R; i++) {
- for (int j = 0; j < S; j++)
- putchar(grid[i][j] == 1? 'X' : (grid[i][j] == 2 ? 'O' : ' '));
- putchar('\n');
- }
-
- printf("CUT\n");
-
- // display sol
- for (int i= 0 ; i < M; i++) {
- if (fposr[i] >= 0)
- printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]);
- else
- printf("x\n");
- }
-
- return 0;
-}
-
diff --git a/a3nm/final b/a3nm/final
@@ -0,0 +1,625 @@
+10 37 38
+5 5 6
+3 97 16
+x
+x
+3 73 28
+x
+14 87 17
+5 78 19
+x
+14 51 37
+10 83 30
+x
+13 79 11
+5 15 22
+0 96 18
+6 98 7
+11 28 36
+2 35 23
+4 39 10
+5 75 31
+x
+x
+13 5 9
+10 29 36
+12 96 43
+x
+x
+11 50 24
+5 98 8
+6 63 5
+5 10 14
+1 25 5
+4 68 6
+2 88 6
+1 49 44
+x
+3 95 13
+x
+x
+12 46 28
+4 5 13
+12 90 23
+11 23 31
+11 99 3
+3 86 2
+14 23 15
+x
+11 62 1
+3 83 36
+12 42 4
+0 39 1
+4 93 43
+x
+7 67 39
+x
+1 15 27
+5 20 30
+2 99 1
+14 28 34
+2 15 24
+0 41 15
+0 71 4
+13 98 21
+12 30 39
+3 58 14
+8 78 38
+7 25 38
+x
+9 90 27
+6 72 37
+x
+4 20 35
+x
+x
+12 99 34
+6 59 29
+15 98 39
+10 91 20
+2 57 28
+14 79 28
+7 35 42
+0 31 32
+6 87 34
+0 92 10
+x
+12 71 10
+x
+13 53 31
+15 0 3
+11 18 28
+8 94 25
+4 49 9
+2 20 32
+7 95 26
+6 95 41
+x
+x
+12 77 29
+5 57 16
+1 92 12
+10 15 21
+0 11 21
+15 99 19
+x
+14 47 31
+8 84 36
+3 80 42
+x
+10 10 23
+6 76 6
+x
+14 99 4
+4 10 21
+12 5 9
+x
+10 97 25
+3 24 43
+x
+10 0 7
+4 15 29
+x
+5 53 40
+0 5 13
+8 0 7
+12 87 44
+10 93 28
+12 25 41
+13 15 25
+11 88 39
+x
+3 36 7
+11 5 12
+5 84 7
+6 93 14
+0 83 33
+7 97 28
+11 65 13
+x
+14 76 20
+7 82 13
+5 72 15
+8 68 3
+x
+1 33 28
+9 51 23
+6 47 39
+14 93 32
+15 87 1
+0 0 5
+15 93 44
+6 69 31
+x
+8 72 5
+8 34 21
+5 49 33
+x
+0 90 0
+7 73 4
+7 79 20
+8 81 32
+1 0 3
+x
+10 68 14
+5 93 34
+12 50 19
+x
+x
+12 80 14
+10 98 12
+5 65 29
+5 39 26
+12 92 36
+9 99 15
+x
+x
+3 10 27
+x
+10 5 15
+6 23 32
+7 20 30
+9 5 12
+2 53 11
+3 15 15
+12 68 27
+13 60 36
+x
+8 58 2
+8 5 4
+x
+1 59 37
+12 83 15
+x
+0 35 17
+11 98 10
+12 62 2
+15 91 28
+8 9 15
+1 55 18
+1 66 33
+9 95 29
+9 43 5
+14 38 33
+0 52 25
+11 54 34
+3 50 10
+13 95 4
+11 42 6
+5 97 24
+10 94 27
+9 98 11
+x
+x
+x
+x
+10 89 29
+10 80 8
+5 30 41
+x
+11 68 11
+1 88 26
+4 72 41
+3 67 5
+x
+x
+14 59 25
+14 91 1
+x
+6 43 3
+2 97 26
+x
+3 99 0
+8 46 42
+4 87 19
+13 77 24
+x
+5 45 10
+x
+13 0 2
+1 90 2
+13 91 38
+11 90 7
+x
+1 10 19
+10 18 31
+11 82 27
+6 34 38
+3 19 35
+14 82 16
+15 57 38
+13 10 17
+4 96 16
+1 94 39
+11 46 29
+5 96 2
+14 95 0
+14 43 41
+3 29 29
+x
+x
+15 65 27
+15 61 8
+4 53 2
+x
+7 88 37
+9 87 32
+9 81 26
+2 62 43
+13 93 0
+8 92 19
+15 96 14
+11 97 22
+x
+3 62 24
+7 52 17
+2 74 22
+4 95 17
+x
+7 96 36
+10 34 44
+12 65 12
+14 97 36
+14 67 21
+6 82 36
+x
+1 96 40
+9 69 25
+x
+x
+6 97 17
+9 92 6
+7 99 2
+12 35 20
+11 94 35
+7 64 16
+6 8 8
+13 46 16
+9 47 38
+1 20 35
+2 86 25
+x
+x
+14 64 19
+x
+9 38 24
+14 73 9
+14 3 2
+13 49 30
+12 20 33
+4 79 32
+10 24 39
+x
+6 91 21
+8 75 40
+2 47 9
+9 59 31
+13 74 28
+x
+10 65 42
+x
+8 24 39
+15 69 22
+4 0 5
+x
+13 64 44
+9 55 13
+5 95 3
+10 61 33
+1 53 8
+7 92 15
+3 5 19
+7 48 41
+14 33 42
+1 85 1
+9 72 43
+7 5 6
+10 74 24
+10 49 37
+x
+6 85 30
+3 38 8
+8 88 26
+15 37 35
+x
+15 24 34
+x
+3 46 3
+7 98 5
+0 16 29
+1 98 31
+3 77 38
+8 62 8
+2 5 8
+5 81 12
+2 90 4
+8 54 6
+13 28 41
+14 55 7
+0 21 37
+11 33 44
+2 94 2
+4 34 40
+9 96 34
+8 86 24
+0 48 34
+x
+8 50 9
+5 88 9
+11 77 33
+11 58 30
+7 90 25
+6 0 1
+x
+15 84 0
+7 0 0
+9 20 0
+0 77 43
+0 74 40
+8 99 14
+0 26 44
+11 38 19
+15 32 42
+9 24 36
+0 88 28
+1 62 4
+x
+10 40 22
+13 33 34
+x
+0 60 3
+6 66 9
+x
+7 44 34
+x
+14 70 29
+x
+2 96 18
+8 42 35
+x
+9 84 39
+x
+14 8 10
+x
+10 71 32
+2 65 7
+12 74 18
+9 29 44
+6 89 42
+4 91 22
+13 88 15
+9 63 9
+15 46 43
+0 68 23
+x
+3 42 1
+1 28 43
+13 42 40
+5 86 20
+7 30 27
+4 45 25
+11 0 4
+1 5 11
+15 81 41
+2 77 17
+13 99 35
+x
+9 97 33
+2 25 40
+9 0 4
+0 94 41
+13 82 19
+12 54 35
+5 43 5
+15 97 29
+2 0 0
+12 0 1
+11 10 20
+x
+9 78 1
+9 34 30
+4 82 18
+x
+x
+2 30 37
+5 25 38
+8 97 37
+8 29 43
+x
+4 29 37
+x
+x
+15 75 12
+1 40 7
+4 76 14
+11 96 38
+5 99 18
+5 69 21
+1 97 9
+5 35 37
+x
+8 38 12
+12 15 25
+x
+14 94 30
+1 73 24
+10 53 43
+8 90 11
+x
+x
+7 60 40
+5 90 11
+x
+x
+x
+1 38 42
+1 99 38
+x
+0 56 39
+x
+12 94 37
+1 76 41
+15 78 2
+x
+7 70 23
+6 99 43
+13 20 33
+15 5 20
+12 98 13
+13 71 13
+11 74 8
+x
+x
+4 85 42
+5 0 17
+9 10 20
+1 79 13
+3 93 32
+3 0 11
+7 56 1
+14 89 40
+0 86 22
+8 65 44
+13 96 39
+2 39 44
+10 99 6
+14 96 3
+x
+6 39 18
+9 66 10
+13 68 18
+0 98 30
+6 51 22
+8 19 31
+14 18 26
+7 84 8
+11 15 40
+x
+15 19 26
+2 43 36
+15 9 10
+12 10 17
+15 50 32
+10 96 35
+9 15 28
+2 98 42
+3 89 33
+0 99 16
+6 79 25
+4 99 20
+6 6 19
+12 39 31
+13 25 29
+10 57 10
+x
+x
+13 56 20
+2 71 3
+15 72 33
+7 86 35
+15 95 31
+15 29 17
+7 76 44
+8 96 41
+x
+x
+4 98 4
+x
+x
+11 92 23
+9 75 7
+x
+x
+3 65 6
+15 14 18
+13 85 6
+x
+8 95 20
+6 13 16
+7 15 22
+12 97 40
+3 91 18
+1 82 34
+12 85 30
+x
+x
+2 83 35
+4 89 3
+6 18 24
+x
+9 94 22
+13 38 14
+13 97 27
+11 71 26
+5 61 0
+2 10 16
+0 64 26
+14 13 18
+x
+4 24 38
+x
+10 77 16
+x
+x
+8 14 23
+2 49 21
+2 68 30
+6 55 12
+4 41 39
+4 64 15
+x
+x
+6 28 40
+0 43 42
+7 94 21
+11 85 43
+x
+14 0 27
+10 86 34
+2 80 41
+x
+3 71 44
+4 61 11
+12 58 32
+7 10 14
+x
+14 85 14
+4 57 27
+11 79 0
+15 89 5
+10 44 13
+7 40 11
+1 44 0
+0 80 35
+1 70 36
+x
+2 92 33
+x
+x
+x
+3 53 26
+x
+15 54 23
+4 97 23
+3 34 12
+15 42 16
diff --git a/a3nm/final.cpp b/a3nm/final.cpp
@@ -0,0 +1,291 @@
+#include <vector>
+#include <cstdio>
+#include <algorithm>
+#include <map>
+#include <time.h>
+
+// g++ -o 400 -O2 470_gives_400.cpp
+// ./400 470 < ../dc.in |tail -1000 | grep -A999999 WOOT | sed 1d > my400
+
+using namespace std;
+
+#define MAXN 1002
+
+typedef pair<int,int> pii;
+typedef pair<int,pii> piii;
+
+struct Server{
+ int id, z, c;
+ Server(int id=0, int z=0, int c=0) : id(id), z(z), c(c) {}
+ bool operator< (const Server &s) const{
+ if (z*s.c == s.z*c) return z > s.z;
+ return z*s.c < s.z*c;
+ }
+};
+
+struct comp{
+ bool operator() (const Server &a, const Server &b){
+ if (a.z == b.z)
+ return a.c > b.c;
+ return a.z > b.z;
+ }
+};
+
+int R, S, U, P, M;
+vector<Server> serv;
+Server oserv[MAXN];
+char grid[MAXN][MAXN]; // row, col
+int capa[MAXN];
+int space[MAXN]; // free space
+int gcapa[MAXN][MAXN]; // row, group
+int fposr[MAXN], fposc[MAXN], fgroup[MAXN];
+
+
+int swap(int rsl, int rsh) {
+ int tmp;
+ int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh];
+ tmp = fposr[rsh];
+ fposr[rsh] = fposr[rsl];
+ fposr[rsl] = tmp;
+ tmp = fposc[rsh];
+ fposc[rsh] = fposc[rsl];
+ fposc[rsl] = tmp;
+ tmp = fgroup[rsh];
+ fgroup[rsh] = fgroup[rsl];
+ fgroup[rsl] = tmp;
+ gcapa[rh][gh] += oserv[rsl].c - oserv[rsh].c;
+ gcapa[rl][gl] += oserv[rsh].c - oserv[rsl].c;
+ capa[gh] += oserv[rsl].c - oserv[rsh].c;
+ capa[gl] += oserv[rsh].c - oserv[rsl].c;
+}
+
+
+int gapas(int fguar[MAXN]) {
+ for (int j = 0; j < P; j++)
+ fguar[j] = capa[j];
+ for (int j = 0; j < R; j++)
+ for (int k = 0; k < P; k++)
+ fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]);
+ int mfguar = fguar[0];
+ int g = 0;
+ for (int j = 0; j < P; j++)
+ if (fguar[j] < mfguar) {
+ mfguar = fguar[j];
+ g = j;
+ }
+ return g;
+}
+
+
+
+int main(int argc, char **argv) {
+ scanf("%d", &R);
+ scanf("%d", &S);
+ scanf("%d", &U);
+ scanf("%d", &P);
+ scanf("%d", &M);
+ srand(45);
+ for (int i = 0; i < R; i++)
+ space[i] = S;
+ for (int i = 0; i < U; i++) {
+ int r, s;
+ scanf("%d", &r);
+ scanf("%d", &s);
+ grid[r][s] = 1;
+ space[r] -= 1;
+ }
+ for (int i = 0; i < M; i++) {
+ int z, c;
+ scanf("%d", &z);
+ scanf("%d", &c);
+ serv.push_back(Server(i, z, c));
+ oserv[i] = Server(i, z, c);
+ }
+
+ sort(serv.begin(), serv.end());
+
+ // now keep only the servers we will use
+ int free = R * S - U;
+ int besttcapa = 0;
+
+ int i;
+ for (i = 0; i < M; i++) {
+ free -= serv[i].c; // should be .z, but???!
+ if (free >= 0)
+ besttcapa += serv[i].c;
+ if (free <= 0)
+ break;
+ }
+
+ // for i in `seq 500`; do echo -n "$i "; ./a.out $i < ../dc.in | grep FINAL | cut -d ' ' -f2 ; done | sort -k2,2n
+ // USE 470
+ sort(serv.begin(), serv.begin() + i + atoi(argv[1]), comp());
+
+ int ftcapa = 0;
+ for (int i = 0; i < M; i++) {
+ fposr[i] = fposc[i] = fgroup[i] = -1;
+ }
+
+ for (int i = 0; i < M; i++) {
+ // place server i
+ 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);
+ // 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];
+ int 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 wherecol = -1, whererow = -1;
+ for (int j = 0; j < R; j++) {
+ printf("gcapa of row is %d and space is %d\n", gcapa[j][idx], space[j]);
+ v.push_back(make_pair<int, int>(MAXN * gcapa[j][idx] + (MAXN-1) - space[j], 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;
+ int k;
+ for (k = 0; k < S; k++) {
+ if (!grid[row][k])
+ contig++;
+ else
+ contig = 0;
+ if (contig == serv[i].z) {
+ // ok, can place
+ break;
+ }
+ }
+ if (contig == serv[i].z) {
+ // do place
+ wherecol = k - (serv[i].z - 1);
+ whererow = row;
+ break;
+ }
+ }
+ if (wherecol >= 0 && whererow >= 0) {
+ // yeah, we can place it! update
+ capa[idx] += serv[i].c;
+ gcapa[whererow][idx] += serv[i].c;
+ for (int k = 0; k < serv[i].z; k++)
+ grid[whererow][wherecol+k] = 2;
+ fposr[serv[i].id] = whererow;
+ fposc[serv[i].id] = wherecol;
+ fgroup[serv[i].id] = idx;
+ space[whererow] -= serv[i].z;
+ ftcapa += serv[i].c;
+ } else {
+ printf("CANNOT PLACE!!\n");
+ }
+ }
+
+ int MAXT = 1000000000;
+ for (int nsw = 0; nsw < MAXT; nsw++) {
+ int rsl = rand() % M;
+ int rsh = rand() % M;
+ int rsl2 = rand() % M;
+ int rsh2 = rand() % M;
+ if (rsl == rsh || rsl == rsl2 || rsl == rsh2 || rsh == rsl2 || rsh == rsh2 || rsl2 == rsh2)
+ continue;
+ if (oserv[rsl].z != oserv[rsh].z)
+ continue;
+ if (oserv[rsl2].z != oserv[rsh2].z)
+ continue;
+ if (fgroup[rsl] < 0 || fgroup[rsh] < 0)
+ continue;
+ if (fgroup[rsl2] < 0 || fgroup[rsh2] < 0)
+ continue;
+ int thefguar[MAXN];
+ int wg = gapas(thefguar);
+ int oldcapa = thefguar[wg];
+
+ printf("GCAPA %d\n", oldcapa);
+
+ // try swap
+ // int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh];
+ // printf("swap servers %d %d\n", rsl, rsh);
+ // printf("swap rows %d %d\n", rl, rh);
+ // printf("capas on rows are %d %d\n", gcapa[rl][gl], gcapa[rh][gh]);
+ // printf("their groups are: %d %d\n", fgroup[rsl], fgroup[rsh]);
+ // printf("their capas are: %d %d\n", oserv[rsl].c, oserv[rsh].c);
+ // printf("their sizes are: %d %d\n", oserv[rsl].z, oserv[rsh].z);
+
+ // do swap
+ int tmp;
+ swap(rsl, rsh);
+ swap(rsl2, rsh2);
+
+ int nwg = gapas(thefguar);
+ int newcapa = thefguar[nwg];
+
+ printf("GCAPA is now: %d\n", newcapa);
+
+ if (newcapa >= oldcapa) {
+ if (newcapa > oldcapa) {
+ printf("WOOT\n");
+ for (int i= 0 ; i < M; i++) {
+ if (fposr[i] >= 0)
+ printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]);
+ else
+ printf("x\n");
+ }
+ exit(0);
+ }
+ printf("KEEEEEP\n");
+ continue;
+ }
+
+ // rollback
+ swap(rsh, rsl);
+ swap(rsh2, rsl2);
+ }
+
+ int fguar[MAXN];
+ for (int j = 0; j < P; j++)
+ fguar[j] = capa[j];
+ for (int j = 0; j < R; j++)
+ for (int k = 0; k < P; k++)
+ fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]);
+ int mfguar = fguar[0];
+ int idx = 0;
+ for (int j = 0; j < P; j++)
+ if (fguar[j] < mfguar) {
+ mfguar = fguar[j];
+ idx = j;
+ }
+
+ printf("best %d placed %d\n", besttcapa, ftcapa);
+ for (int i = 0; i < P; i++)
+ printf("guar for %d: %d\n", i, fguar[i]);
+ printf("FINAL: %d\n", mfguar);
+
+ for (int i = 0; i < R; i++) {
+ for (int j = 0; j < S; j++)
+ putchar(grid[i][j] == 1? 'X' : (grid[i][j] == 2 ? 'O' : ' '));
+ putchar('\n');
+ }
+
+ printf("CUT\n");
+
+ // display sol
+ for (int i= 0 ; i < M; i++) {
+ if (fposr[i] >= 0)
+ printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]);
+ else
+ printf("x\n");
+ }
+
+ return 0;
+}
+
