commit 25f03d11fed7f301bf87869597731f8a3d408f66
parent da8c293518565c07bafc6146903ada8e32ad3310
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 12 Mar 2015 23:12:13 +0100
selection
Diffstat:
16 files changed, 2186 insertions(+), 2186 deletions(-)
diff --git a/README.md b/README.md
@@ -1 +0,0 @@
-# ens-ulm-1
diff --git a/a3nm/470_gives_399.cpp b/a3nm/470_gives_399.cpp
@@ -1,186 +0,0 @@
-#include <vector>
-#include <cstdio>
-#include <algorithm>
-#include <map>
-
-// Compile WITHOUT OPTIMS!!
-
-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 main(int argc, char **argv) {
- int R, S, U, P, M;
- vector<Server> serv;
- 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];
-
- scanf("%d", &R);
- scanf("%d", &S);
- scanf("%d", &U);
- scanf("%d", &P);
- scanf("%d", &M);
- 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));
- }
-
- 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 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];
- for (int j = 0; j < P; j++)
- if (fguar[j] < mfguar) {
- mfguar = fguar[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
@@ -1,625 +0,0 @@
-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
@@ -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/server.cpp b/a3nm/server.cpp
@@ -1,290 +0,0 @@
-#include <vector>
-#include <cstdio>
-#include <algorithm>
-#include <map>
-#include <time.h>
-
-// Compile WITHOUT OPTIMS!!
-
-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/useless.c b/a3nm/useless.c
@@ -1,87 +0,0 @@
-
- int did = 1;
- while (did) {
- did = 0;
- 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;
- }
- printf("guar is %d, optimize worst group: %d\n", mfguar, g);
- // optimize g
- vector<pii> vv;
- for (int r = 0; r < R; r++)
- vv.push_back(make_pair(gcapa[r][g], r));
- sort(vv.begin(), vv.end());
- for (int rh = R - 1; rh >= 0; rh--) {
- if (vv[rh].first < vv[R-1].first)
- break;
- for (int rl = 0; rl < rh; rl++) {
- //printf("swap in rl %d rh %d\n", rl, rh);
- vector<int> sl, sh;
- for (int s = 0; s < M; s++) {
- if (fgroup[s] != g)
- continue;
- //printf("aoeu servera %d is in %d\n", s, fposr[s]);
- if (fposr[s] == vv[rh].second)
- sh.push_back(s);
- if (fposr[s] == vv[rl].second)
- sl.push_back(s);
- }
- int tcapal = 0;
- for (unsigned int ssl = 0; ssl < sl.size(); ssl++)
- tcapal += oserv[sl[ssl]].c;
- printf("calculated capa of l as %d and should be %d\n", tcapal, gcapa[vv[rl].second][g]);
- //printf("aoeu i have %d %d servers\n", sl.size(), sh.size());
- for (unsigned int ssl = 0; ssl < sl.size(); ssl++) {
- for (unsigned int ssh = 0; ssh < sh.size(); ssh++) {
- int rsh = sh[ssh];
- int rsl = sl[ssl];
- //printf("aoeu soeu wap consider rsl %d rsh %d\n", rsl, rsh);
- // try to swap rsl and rsh
- if (oserv[rsl].z != oserv[rsh].z)
- continue;
- if (oserv[rsh].c <= oserv[rsl].c)
- continue;
- if (gcapa[vv[rl].second][g] + oserv[rsh].c - oserv[rsl].c >= gcapa[vv[rh].second][g])
- continue;
- // can swap
- did = 1;
- printf("swap servers %d %d\n", rsl, rsh);
- printf("swap rows %d %d\n", vv[rl].second, vv[rh].second);
- printf("capas on rows are %d %d\n", gcapa[rl][g], gcapa[rh][g]);
- printf("capas on rows will be %d %d\n", gcapa[rl][g] + oserv[rsh].c - oserv[rsh].c,
- gcapa[rh][g] + oserv[rsl].c - oserv[rsh].c);
- 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;
- tmp = fposr[rsh];
- fposr[rsh] = fposr[rsl];
- fposr[rsl] = tmp;
- tmp = fposc[rsh];
- fposc[rsh] = fposc[rsl];
- fposc[rsl] = tmp;
- gcapa[rh][g] += oserv[rsl].c - oserv[rsh].c;
- gcapa[rl][g] += oserv[rsh].c - oserv[rsl].c;
- break;
- }
- if (did)
- break;
- }
- if (did)
- break;
- }
- if (did)
- break;
- }
- }
diff --git a/dc.in b/dc.in
@@ -1,706 +0,0 @@
-16 100 80 45 625
-10 23
-0 40
-4 40
-3 57
-11 78
-10 82
-14 27
-1 39
-6 75
-0 47
-3 49
-8 8
-0 42
-3 18
-10 39
-8 71
-3 52
-9 42
-12 95
-0 10
-12 89
-11 17
-5 44
-2 48
-15 31
-5 38
-1 48
-1 54
-13 55
-9 65
-12 91
-11 67
-8 57
-15 56
-6 5
-8 83
-13 27
-9 89
-13 78
-9 23
-11 27
-0 73
-3 64
-4 63
-1 27
-3 72
-1 61
-4 44
-10 17
-5 83
-5 92
-3 35
-4 27
-14 98
-10 36
-9 74
-2 73
-11 66
-2 61
-6 7
-15 83
-8 91
-10 95
-13 48
-12 41
-3 66
-0 51
-5 4
-4 28
-3 37
-15 8
-14 2
-5 3
-10 48
-6 33
-14 63
-7 34
-4 23
-3 94
-8 98
-2 28
-5 55
-2 40
-3 18
-1 6
-4 68
-3 18
-2 40
-3 60
-5 25
-4 60
-3 27
-4 24
-3 36
-5 95
-2 26
-1 19
-5 45
-4 56
-1 17
-3 51
-3 15
-2 10
-5 95
-5 45
-1 19
-5 30
-3 18
-4 68
-1 12
-3 27
-5 55
-2 26
-4 32
-2 40
-4 48
-3 18
-2 20
-3 24
-2 12
-4 32
-5 90
-1 8
-4 32
-1 19
-3 36
-4 68
-1 6
-3 33
-3 48
-4 80
-1 11
-2 36
-2 16
-3 33
-2 16
-5 60
-5 65
-1 20
-5 100
-5 90
-1 12
-2 22
-1 11
-5 45
-4 48
-3 60
-5 65
-4 28
-2 40
-3 39
-4 20
-3 39
-5 35
-5 30
-1 14
-4 32
-1 19
-2 28
-4 44
-3 39
-5 40
-4 32
-2 30
-2 20
-4 24
-3 60
-5 30
-2 18
-5 95
-5 50
-1 18
-4 56
-5 75
-1 18
-2 30
-5 35
-1 6
-3 27
-4 64
-2 30
-2 24
-5 90
-1 11
-2 10
-4 60
-2 32
-3 33
-1 6
-5 95
-3 54
-3 21
-1 9
-5 85
-5 95
-2 16
-1 17
-5 55
-4 28
-5 90
-5 85
-5 25
-4 40
-5 85
-5 85
-2 34
-1 18
-5 40
-5 60
-2 34
-2 10
-1 10
-5 100
-2 30
-2 40
-3 60
-1 20
-1 20
-2 12
-3 48
-2 28
-3 33
-3 27
-4 20
-5 65
-4 64
-4 40
-1 15
-2 20
-5 80
-2 18
-3 33
-2 14
-3 60
-4 76
-4 36
-3 15
-2 22
-3 45
-3 36
-2 24
-5 85
-1 6
-3 45
-2 36
-4 60
-2 16
-1 8
-3 54
-1 11
-4 32
-4 48
-2 30
-1 17
-4 24
-3 21
-5 65
-1 8
-5 60
-5 75
-5 70
-5 95
-4 64
-3 54
-3 57
-4 48
-2 16
-4 68
-3 45
-2 12
-2 18
-2 26
-1 8
-4 64
-1 11
-3 33
-2 22
-5 70
-4 72
-4 44
-1 10
-4 72
-5 55
-4 52
-4 32
-2 22
-1 10
-4 44
-1 12
-1 14
-1 11
-3 15
-4 28
-3 15
-2 16
-2 34
-2 34
-5 45
-1 5
-3 60
-2 30
-4 60
-4 80
-1 5
-1 7
-4 56
-2 32
-4 28
-4 64
-1 18
-5 30
-1 9
-4 80
-2 32
-1 16
-4 24
-4 72
-4 24
-5 85
-2 22
-2 26
-2 36
-5 30
-5 75
-5 80
-3 48
-5 45
-5 65
-3 33
-4 36
-5 90
-1 19
-2 24
-4 44
-1 18
-1 8
-4 40
-5 80
-2 10
-5 30
-4 48
-4 64
-4 48
-4 24
-2 32
-2 28
-3 39
-3 48
-2 32
-2 18
-1 8
-1 13
-4 28
-2 24
-4 80
-3 27
-1 8
-2 14
-1 13
-2 40
-3 48
-1 18
-3 54
-3 36
-3 21
-1 20
-3 54
-3 18
-4 20
-1 14
-2 40
-1 17
-4 68
-2 26
-3 36
-5 100
-2 28
-4 64
-5 40
-2 30
-1 7
-1 5
-3 42
-2 16
-4 64
-3 45
-5 85
-4 60
-5 55
-3 45
-5 90
-1 7
-2 32
-3 27
-1 16
-4 80
-3 36
-1 5
-3 30
-2 12
-5 90
-3 60
-5 75
-2 10
-4 48
-4 76
-1 14
-4 48
-1 10
-2 30
-5 50
-4 36
-5 90
-3 36
-2 20
-5 55
-3 60
-4 52
-3 24
-2 34
-4 68
-2 26
-5 60
-4 24
-5 70
-2 14
-3 39
-1 20
-5 60
-1 18
-3 48
-3 27
-5 100
-2 26
-2 38
-3 57
-5 45
-4 44
-5 65
-5 45
-2 28
-5 60
-1 13
-2 26
-3 36
-2 16
-4 56
-2 34
-1 16
-4 68
-2 30
-5 100
-3 15
-3 42
-5 90
-3 39
-3 48
-3 45
-1 12
-5 50
-4 60
-5 90
-5 55
-2 32
-4 72
-1 6
-4 76
-5 80
-3 18
-4 72
-3 48
-5 25
-4 36
-2 14
-3 42
-4 28
-1 18
-4 32
-5 35
-3 27
-2 10
-5 95
-4 28
-3 30
-3 45
-3 27
-5 40
-2 24
-2 28
-3 60
-2 40
-4 36
-3 45
-4 20
-4 48
-5 45
-4 56
-2 30
-4 60
-4 60
-5 75
-5 75
-2 24
-3 48
-1 9
-4 28
-1 13
-5 65
-5 90
-2 36
-3 51
-4 40
-1 20
-1 20
-5 80
-5 100
-5 50
-4 20
-3 36
-4 60
-3 54
-5 30
-2 10
-5 65
-5 40
-1 18
-5 45
-3 21
-5 45
-3 18
-5 35
-3 45
-4 80
-3 48
-1 11
-1 12
-3 60
-1 10
-3 60
-5 30
-4 52
-5 50
-2 16
-1 18
-3 45
-4 56
-1 17
-2 14
-3 18
-4 32
-2 36
-2 14
-5 25
-5 35
-1 9
-1 15
-1 5
-4 32
-2 14
-1 16
-3 48
-3 51
-3 18
-3 60
-1 17
-5 65
-3 60
-1 12
-3 45
-3 57
-1 6
-4 24
-2 30
-3 30
-5 65
-3 42
-1 16
-5 75
-4 64
-2 24
-2 20
-3 33
-1 11
-4 40
-1 19
-1 18
-1 6
-4 68
-3 42
-3 30
-1 10
-4 68
-5 80
-5 70
-2 28
-2 30
-2 12
-5 50
-4 56
-5 90
-5 90
-4 60
-1 19
-5 45
-1 16
-2 20
-1 18
-3 33
-1 15
-1 16
-2 22
-2 20
-4 68
-3 18
-1 7
-4 60
-2 30
-3 36
-2 34
-1 11
-2 30
-3 45
-1 11
-3 15
-2 16
-1 9
-2 10
-4 28
-2 32
-3 54
-5 30
-5 25
-1 19
-5 70
-3 48
-3 18
-1 10
-5 70
-5 95
-1 18
-2 28
-3 33
-2 20
-2 14
-3 18
-3 57
-2 32
-5 90
-2 14
-1 14
-4 60
-1 17
-3 51
-4 48
-5 70
-4 56
-5 75
-1 6
-3 27
-2 10
-3 27
-3 15
-5 30
-5 90
-4 52
-3 39
-4 76
-3 51
-4 40
-3 21
-1 6
-5 50
-4 52
-1 8
-3 36
-3 21
-2 18
-3 30
-3 51
-4 24
-1 15
-2 32
-4 76
-5 50
-3 21
-2 40
-4 44
-3 60
-2 22
-4 72
-4 72
-4 60
-3 45
-3 30
-2 14
-2 40
-3 24
-1 6
-5 30
-4 72
-5 25
-2 34
-1 11
-1 18
-4 68
diff --git a/demo b/demo
diff --git a/selection/README.md b/selection/README.md
@@ -0,0 +1 @@
+# ens-ulm-1
diff --git a/selection/a3nm/470_gives_399.cpp b/selection/a3nm/470_gives_399.cpp
@@ -0,0 +1,186 @@
+#include <vector>
+#include <cstdio>
+#include <algorithm>
+#include <map>
+
+// Compile WITHOUT OPTIMS!!
+
+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 main(int argc, char **argv) {
+ int R, S, U, P, M;
+ vector<Server> serv;
+ 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];
+
+ scanf("%d", &R);
+ scanf("%d", &S);
+ scanf("%d", &U);
+ scanf("%d", &P);
+ scanf("%d", &M);
+ 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));
+ }
+
+ 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 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];
+ for (int j = 0; j < P; j++)
+ if (fguar[j] < mfguar) {
+ mfguar = fguar[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/selection/a3nm/final b/selection/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/selection/a3nm/final.cpp b/selection/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;
+}
+
diff --git a/selection/a3nm/server.cpp b/selection/a3nm/server.cpp
@@ -0,0 +1,290 @@
+#include <vector>
+#include <cstdio>
+#include <algorithm>
+#include <map>
+#include <time.h>
+
+// Compile WITHOUT OPTIMS!!
+
+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/selection/a3nm/useless.c b/selection/a3nm/useless.c
@@ -0,0 +1,87 @@
+
+ int did = 1;
+ while (did) {
+ did = 0;
+ 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;
+ }
+ printf("guar is %d, optimize worst group: %d\n", mfguar, g);
+ // optimize g
+ vector<pii> vv;
+ for (int r = 0; r < R; r++)
+ vv.push_back(make_pair(gcapa[r][g], r));
+ sort(vv.begin(), vv.end());
+ for (int rh = R - 1; rh >= 0; rh--) {
+ if (vv[rh].first < vv[R-1].first)
+ break;
+ for (int rl = 0; rl < rh; rl++) {
+ //printf("swap in rl %d rh %d\n", rl, rh);
+ vector<int> sl, sh;
+ for (int s = 0; s < M; s++) {
+ if (fgroup[s] != g)
+ continue;
+ //printf("aoeu servera %d is in %d\n", s, fposr[s]);
+ if (fposr[s] == vv[rh].second)
+ sh.push_back(s);
+ if (fposr[s] == vv[rl].second)
+ sl.push_back(s);
+ }
+ int tcapal = 0;
+ for (unsigned int ssl = 0; ssl < sl.size(); ssl++)
+ tcapal += oserv[sl[ssl]].c;
+ printf("calculated capa of l as %d and should be %d\n", tcapal, gcapa[vv[rl].second][g]);
+ //printf("aoeu i have %d %d servers\n", sl.size(), sh.size());
+ for (unsigned int ssl = 0; ssl < sl.size(); ssl++) {
+ for (unsigned int ssh = 0; ssh < sh.size(); ssh++) {
+ int rsh = sh[ssh];
+ int rsl = sl[ssl];
+ //printf("aoeu soeu wap consider rsl %d rsh %d\n", rsl, rsh);
+ // try to swap rsl and rsh
+ if (oserv[rsl].z != oserv[rsh].z)
+ continue;
+ if (oserv[rsh].c <= oserv[rsl].c)
+ continue;
+ if (gcapa[vv[rl].second][g] + oserv[rsh].c - oserv[rsl].c >= gcapa[vv[rh].second][g])
+ continue;
+ // can swap
+ did = 1;
+ printf("swap servers %d %d\n", rsl, rsh);
+ printf("swap rows %d %d\n", vv[rl].second, vv[rh].second);
+ printf("capas on rows are %d %d\n", gcapa[rl][g], gcapa[rh][g]);
+ printf("capas on rows will be %d %d\n", gcapa[rl][g] + oserv[rsh].c - oserv[rsh].c,
+ gcapa[rh][g] + oserv[rsl].c - oserv[rsh].c);
+ 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;
+ tmp = fposr[rsh];
+ fposr[rsh] = fposr[rsl];
+ fposr[rsl] = tmp;
+ tmp = fposc[rsh];
+ fposc[rsh] = fposc[rsl];
+ fposc[rsl] = tmp;
+ gcapa[rh][g] += oserv[rsl].c - oserv[rsh].c;
+ gcapa[rl][g] += oserv[rsh].c - oserv[rsl].c;
+ break;
+ }
+ if (did)
+ break;
+ }
+ if (did)
+ break;
+ }
+ if (did)
+ break;
+ }
+ }
diff --git a/selection/dc.in b/selection/dc.in
@@ -0,0 +1,706 @@
+16 100 80 45 625
+10 23
+0 40
+4 40
+3 57
+11 78
+10 82
+14 27
+1 39
+6 75
+0 47
+3 49
+8 8
+0 42
+3 18
+10 39
+8 71
+3 52
+9 42
+12 95
+0 10
+12 89
+11 17
+5 44
+2 48
+15 31
+5 38
+1 48
+1 54
+13 55
+9 65
+12 91
+11 67
+8 57
+15 56
+6 5
+8 83
+13 27
+9 89
+13 78
+9 23
+11 27
+0 73
+3 64
+4 63
+1 27
+3 72
+1 61
+4 44
+10 17
+5 83
+5 92
+3 35
+4 27
+14 98
+10 36
+9 74
+2 73
+11 66
+2 61
+6 7
+15 83
+8 91
+10 95
+13 48
+12 41
+3 66
+0 51
+5 4
+4 28
+3 37
+15 8
+14 2
+5 3
+10 48
+6 33
+14 63
+7 34
+4 23
+3 94
+8 98
+2 28
+5 55
+2 40
+3 18
+1 6
+4 68
+3 18
+2 40
+3 60
+5 25
+4 60
+3 27
+4 24
+3 36
+5 95
+2 26
+1 19
+5 45
+4 56
+1 17
+3 51
+3 15
+2 10
+5 95
+5 45
+1 19
+5 30
+3 18
+4 68
+1 12
+3 27
+5 55
+2 26
+4 32
+2 40
+4 48
+3 18
+2 20
+3 24
+2 12
+4 32
+5 90
+1 8
+4 32
+1 19
+3 36
+4 68
+1 6
+3 33
+3 48
+4 80
+1 11
+2 36
+2 16
+3 33
+2 16
+5 60
+5 65
+1 20
+5 100
+5 90
+1 12
+2 22
+1 11
+5 45
+4 48
+3 60
+5 65
+4 28
+2 40
+3 39
+4 20
+3 39
+5 35
+5 30
+1 14
+4 32
+1 19
+2 28
+4 44
+3 39
+5 40
+4 32
+2 30
+2 20
+4 24
+3 60
+5 30
+2 18
+5 95
+5 50
+1 18
+4 56
+5 75
+1 18
+2 30
+5 35
+1 6
+3 27
+4 64
+2 30
+2 24
+5 90
+1 11
+2 10
+4 60
+2 32
+3 33
+1 6
+5 95
+3 54
+3 21
+1 9
+5 85
+5 95
+2 16
+1 17
+5 55
+4 28
+5 90
+5 85
+5 25
+4 40
+5 85
+5 85
+2 34
+1 18
+5 40
+5 60
+2 34
+2 10
+1 10
+5 100
+2 30
+2 40
+3 60
+1 20
+1 20
+2 12
+3 48
+2 28
+3 33
+3 27
+4 20
+5 65
+4 64
+4 40
+1 15
+2 20
+5 80
+2 18
+3 33
+2 14
+3 60
+4 76
+4 36
+3 15
+2 22
+3 45
+3 36
+2 24
+5 85
+1 6
+3 45
+2 36
+4 60
+2 16
+1 8
+3 54
+1 11
+4 32
+4 48
+2 30
+1 17
+4 24
+3 21
+5 65
+1 8
+5 60
+5 75
+5 70
+5 95
+4 64
+3 54
+3 57
+4 48
+2 16
+4 68
+3 45
+2 12
+2 18
+2 26
+1 8
+4 64
+1 11
+3 33
+2 22
+5 70
+4 72
+4 44
+1 10
+4 72
+5 55
+4 52
+4 32
+2 22
+1 10
+4 44
+1 12
+1 14
+1 11
+3 15
+4 28
+3 15
+2 16
+2 34
+2 34
+5 45
+1 5
+3 60
+2 30
+4 60
+4 80
+1 5
+1 7
+4 56
+2 32
+4 28
+4 64
+1 18
+5 30
+1 9
+4 80
+2 32
+1 16
+4 24
+4 72
+4 24
+5 85
+2 22
+2 26
+2 36
+5 30
+5 75
+5 80
+3 48
+5 45
+5 65
+3 33
+4 36
+5 90
+1 19
+2 24
+4 44
+1 18
+1 8
+4 40
+5 80
+2 10
+5 30
+4 48
+4 64
+4 48
+4 24
+2 32
+2 28
+3 39
+3 48
+2 32
+2 18
+1 8
+1 13
+4 28
+2 24
+4 80
+3 27
+1 8
+2 14
+1 13
+2 40
+3 48
+1 18
+3 54
+3 36
+3 21
+1 20
+3 54
+3 18
+4 20
+1 14
+2 40
+1 17
+4 68
+2 26
+3 36
+5 100
+2 28
+4 64
+5 40
+2 30
+1 7
+1 5
+3 42
+2 16
+4 64
+3 45
+5 85
+4 60
+5 55
+3 45
+5 90
+1 7
+2 32
+3 27
+1 16
+4 80
+3 36
+1 5
+3 30
+2 12
+5 90
+3 60
+5 75
+2 10
+4 48
+4 76
+1 14
+4 48
+1 10
+2 30
+5 50
+4 36
+5 90
+3 36
+2 20
+5 55
+3 60
+4 52
+3 24
+2 34
+4 68
+2 26
+5 60
+4 24
+5 70
+2 14
+3 39
+1 20
+5 60
+1 18
+3 48
+3 27
+5 100
+2 26
+2 38
+3 57
+5 45
+4 44
+5 65
+5 45
+2 28
+5 60
+1 13
+2 26
+3 36
+2 16
+4 56
+2 34
+1 16
+4 68
+2 30
+5 100
+3 15
+3 42
+5 90
+3 39
+3 48
+3 45
+1 12
+5 50
+4 60
+5 90
+5 55
+2 32
+4 72
+1 6
+4 76
+5 80
+3 18
+4 72
+3 48
+5 25
+4 36
+2 14
+3 42
+4 28
+1 18
+4 32
+5 35
+3 27
+2 10
+5 95
+4 28
+3 30
+3 45
+3 27
+5 40
+2 24
+2 28
+3 60
+2 40
+4 36
+3 45
+4 20
+4 48
+5 45
+4 56
+2 30
+4 60
+4 60
+5 75
+5 75
+2 24
+3 48
+1 9
+4 28
+1 13
+5 65
+5 90
+2 36
+3 51
+4 40
+1 20
+1 20
+5 80
+5 100
+5 50
+4 20
+3 36
+4 60
+3 54
+5 30
+2 10
+5 65
+5 40
+1 18
+5 45
+3 21
+5 45
+3 18
+5 35
+3 45
+4 80
+3 48
+1 11
+1 12
+3 60
+1 10
+3 60
+5 30
+4 52
+5 50
+2 16
+1 18
+3 45
+4 56
+1 17
+2 14
+3 18
+4 32
+2 36
+2 14
+5 25
+5 35
+1 9
+1 15
+1 5
+4 32
+2 14
+1 16
+3 48
+3 51
+3 18
+3 60
+1 17
+5 65
+3 60
+1 12
+3 45
+3 57
+1 6
+4 24
+2 30
+3 30
+5 65
+3 42
+1 16
+5 75
+4 64
+2 24
+2 20
+3 33
+1 11
+4 40
+1 19
+1 18
+1 6
+4 68
+3 42
+3 30
+1 10
+4 68
+5 80
+5 70
+2 28
+2 30
+2 12
+5 50
+4 56
+5 90
+5 90
+4 60
+1 19
+5 45
+1 16
+2 20
+1 18
+3 33
+1 15
+1 16
+2 22
+2 20
+4 68
+3 18
+1 7
+4 60
+2 30
+3 36
+2 34
+1 11
+2 30
+3 45
+1 11
+3 15
+2 16
+1 9
+2 10
+4 28
+2 32
+3 54
+5 30
+5 25
+1 19
+5 70
+3 48
+3 18
+1 10
+5 70
+5 95
+1 18
+2 28
+3 33
+2 20
+2 14
+3 18
+3 57
+2 32
+5 90
+2 14
+1 14
+4 60
+1 17
+3 51
+4 48
+5 70
+4 56
+5 75
+1 6
+3 27
+2 10
+3 27
+3 15
+5 30
+5 90
+4 52
+3 39
+4 76
+3 51
+4 40
+3 21
+1 6
+5 50
+4 52
+1 8
+3 36
+3 21
+2 18
+3 30
+3 51
+4 24
+1 15
+2 32
+4 76
+5 50
+3 21
+2 40
+4 44
+3 60
+2 22
+4 72
+4 72
+4 60
+3 45
+3 30
+2 14
+2 40
+3 24
+1 6
+5 30
+4 72
+5 25
+2 34
+1 11
+1 18
+4 68
diff --git a/selection/demo b/selection/demo
