commit 932fcb2d61924d69965b62f2088293a70ea1f9a4
parent 776ec69bfb4433c2e7b34412eb2e8014a74c6bd2
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 12 Mar 2015 22:01:57 +0100
add complex useless code
Diffstat:
| a3nm/server.cpp | | | 121 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------ |
| a3nm/useless.c | | | 87 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 190 insertions(+), 18 deletions(-)
diff --git a/a3nm/server.cpp b/a3nm/server.cpp
@@ -29,15 +29,16 @@ struct comp{
}
};
-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];
+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 main(int argc, char **argv) {
scanf("%d", &R);
scanf("%d", &S);
scanf("%d", &U);
@@ -57,6 +58,7 @@ int main(int argc, char **argv) {
scanf("%d", &z);
scanf("%d", &c);
serv.push_back(Server(i, z, c));
+ oserv[i] = Server(i, z, c);
}
sort(serv.begin(), serv.end());
@@ -67,29 +69,25 @@ int main(int argc, char **argv) {
int i;
for (i = 0; i < M; i++) {
- free -= serv[i].z; // should be .z, but???!
+ free -= serv[i].c; // should be .z, but???!
if (free >= 0)
besttcapa += serv[i].c;
- if (free == 0)
+ if (free <= 0)
break;
- if (free < 0) {
- free += serv[i].z; // undo
- }
}
// 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(), min(serv.begin() + i + atoi(argv[1]), serv.end()), comp());
+ 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;
}
- free = R * S - U;
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, I have free %d and capa %d\n", i, serv[i].id, serv[i].c, serv[i].z, 1. * serv[i].c/serv[i].z, free, ftcapa);
+ 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++)
@@ -146,13 +144,98 @@ int main(int argc, char **argv) {
fgroup[serv[i].id] = idx;
space[whererow] -= serv[i].z;
ftcapa += serv[i].c;
- free -= serv[i].z;
} else {
printf("CANNOT PLACE!!\n");
}
}
-
+ 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;
+ }
+ }
+
int fguar[MAXN];
for (int j = 0; j < P; j++)
fguar[j] = capa[j];
@@ -160,9 +243,11 @@ int main(int argc, char **argv) {
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);
diff --git a/a3nm/useless.c b/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;
+ }
+ }
