ens-ulm-1-2015

google hashcode 2015 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1-2015/
Log | Files | Refs

final.cpp (7227B)


      1 #include <vector>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <map>
      5 #include <time.h>
      6 
      7 // g++ -o 400 -O2 470_gives_400.cpp
      8 // ./400 470 < ../dc.in |tail -1000 | grep -A999999 WOOT | sed 1d > my400
      9 
     10 using namespace std;
     11 
     12 #define MAXN 1002
     13 
     14 typedef pair<int,int> pii;
     15 typedef pair<int,pii> piii;
     16 
     17 struct Server{
     18    int id, z, c;
     19    Server(int id=0, int z=0, int c=0) : id(id), z(z), c(c) {}
     20    bool operator< (const Server &s) const{
     21       if (z*s.c == s.z*c) return z > s.z;
     22       return z*s.c < s.z*c;
     23    }
     24 };
     25 
     26 struct comp{
     27    bool operator() (const Server &a, const Server &b){
     28       if (a.z == b.z)
     29         return a.c > b.c;
     30       return a.z > b.z;
     31    }
     32 };
     33 
     34 int R, S, U, P, M;
     35 vector<Server> serv;
     36 Server oserv[MAXN];
     37 char grid[MAXN][MAXN]; // row, col
     38 int capa[MAXN];
     39 int space[MAXN]; // free space
     40 int gcapa[MAXN][MAXN]; // row, group
     41 int fposr[MAXN], fposc[MAXN], fgroup[MAXN];
     42 
     43 
     44 int swap(int rsl, int rsh) {
     45   int tmp;
     46   int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh];
     47   tmp = fposr[rsh];
     48   fposr[rsh] = fposr[rsl];
     49   fposr[rsl] = tmp;
     50   tmp = fposc[rsh];
     51   fposc[rsh] = fposc[rsl];
     52   fposc[rsl] = tmp;
     53   tmp = fgroup[rsh];
     54   fgroup[rsh] = fgroup[rsl];
     55   fgroup[rsl] = tmp;
     56   gcapa[rh][gh] += oserv[rsl].c - oserv[rsh].c;
     57   gcapa[rl][gl] += oserv[rsh].c - oserv[rsl].c;
     58   capa[gh] += oserv[rsl].c - oserv[rsh].c;
     59   capa[gl] += oserv[rsh].c - oserv[rsl].c;
     60 }
     61 
     62 
     63 int gapas(int fguar[MAXN]) {
     64   for (int j = 0; j < P; j++)
     65     fguar[j] = capa[j];
     66   for (int j = 0; j < R; j++)
     67     for (int k = 0; k < P; k++)
     68       fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]);
     69   int mfguar = fguar[0];
     70   int g = 0;
     71   for (int j = 0; j < P; j++)
     72     if (fguar[j] < mfguar) {
     73       mfguar = fguar[j];
     74       g = j;
     75     }
     76   return g;
     77 }
     78 
     79 
     80 
     81 int main(int argc, char **argv) {
     82   scanf("%d", &R);
     83   scanf("%d", &S);
     84   scanf("%d", &U);
     85   scanf("%d", &P);
     86   scanf("%d", &M);
     87   srand(45);
     88   for (int i = 0; i < R; i++)
     89     space[i] = S;
     90   for (int i = 0; i < U; i++) {
     91     int r, s;
     92     scanf("%d", &r);
     93     scanf("%d", &s);
     94     grid[r][s] = 1;
     95     space[r] -= 1;
     96   }
     97   for (int i = 0; i < M; i++) {
     98     int z, c;
     99     scanf("%d", &z);
    100     scanf("%d", &c);
    101     serv.push_back(Server(i, z, c));
    102     oserv[i] = Server(i, z, c);
    103   }
    104 
    105   sort(serv.begin(), serv.end());
    106 
    107   // now keep only the servers we will use
    108   int free = R * S - U;
    109   int besttcapa = 0;
    110 
    111   int i;
    112   for (i = 0; i < M; i++) {
    113     free -= serv[i].c; // should be .z, but???!
    114     if (free >= 0)
    115       besttcapa += serv[i].c;
    116     if (free <= 0)
    117       break;
    118   }
    119 
    120   // for i in `seq 500`; do echo -n "$i "; ./a.out $i < ../dc.in  | grep FINAL | cut -d ' ' -f2 ; done | sort -k2,2n
    121   // USE 470
    122   sort(serv.begin(), serv.begin() + i + atoi(argv[1]), comp());
    123 
    124   int ftcapa = 0;
    125   for (int i = 0; i < M; i++) {
    126     fposr[i] = fposc[i] = fgroup[i] = -1;
    127   }
    128 
    129   for (int i = 0; i < M; i++) {
    130     // place server i
    131     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);
    132     // choose the group with lowest guaranteed
    133     int guar[MAXN];
    134     for (int j = 0; j < P; j++)
    135       guar[j] = capa[j];
    136     for (int j = 0; j < R; j++)
    137       for (int k = 0; k < P; k++)
    138         guar[k] = min(guar[k], capa[k] - gcapa[j][k]);
    139     int mguar = guar[0];
    140     int idx = 0;
    141     for (int j = 0; j < P; j++)
    142       if (guar[j] < mguar) {
    143         mguar = guar[j];
    144         idx = j;
    145       }
    146     // idx is the group
    147     // choose where to place server
    148     vector<pii> v;
    149     int wherecol = -1, whererow = -1;
    150     for (int j = 0; j < R; j++) {
    151       printf("gcapa of row is %d and space is %d\n", gcapa[j][idx], space[j]);
    152       v.push_back(make_pair<int, int>(MAXN * gcapa[j][idx] + (MAXN-1) - space[j], j));
    153     }
    154     sort(v.begin(), v.end());
    155     for (int j = 0; j < R; j++) {
    156       // try to place in row
    157       int row = v[j].second;
    158       int contig = 0;
    159       int k;
    160       for (k = 0; k < S; k++) {
    161         if (!grid[row][k])
    162           contig++;
    163         else
    164           contig = 0;
    165         if (contig == serv[i].z) {
    166           // ok, can place
    167           break;
    168         }
    169       }
    170       if (contig == serv[i].z) {
    171         // do place
    172         wherecol = k - (serv[i].z - 1);
    173         whererow = row;
    174         break;
    175       }
    176     }
    177     if (wherecol >= 0 && whererow >= 0) {
    178       // yeah, we can place it! update
    179       capa[idx] += serv[i].c;
    180       gcapa[whererow][idx] += serv[i].c;
    181       for (int k = 0; k < serv[i].z; k++)
    182         grid[whererow][wherecol+k] = 2;
    183       fposr[serv[i].id] = whererow;
    184       fposc[serv[i].id] = wherecol;
    185       fgroup[serv[i].id] = idx;
    186       space[whererow] -= serv[i].z;
    187       ftcapa += serv[i].c;
    188     } else {
    189       printf("CANNOT PLACE!!\n");
    190     }
    191   }
    192 
    193   int MAXT = 1000000000;
    194   for (int nsw = 0; nsw < MAXT; nsw++) {
    195     int rsl = rand() % M;
    196     int rsh = rand() % M;
    197     int rsl2 = rand() % M;
    198     int rsh2 = rand() % M;
    199     if (rsl == rsh || rsl == rsl2 || rsl == rsh2 || rsh == rsl2 || rsh == rsh2 || rsl2 == rsh2)
    200       continue;
    201     if (oserv[rsl].z != oserv[rsh].z)
    202       continue;
    203     if (oserv[rsl2].z != oserv[rsh2].z)
    204       continue;
    205     if (fgroup[rsl] < 0 || fgroup[rsh] < 0)
    206       continue;
    207     if (fgroup[rsl2] < 0 || fgroup[rsh2] < 0)
    208       continue;
    209     int thefguar[MAXN];
    210     int wg = gapas(thefguar);
    211     int oldcapa = thefguar[wg];
    212 
    213     printf("GCAPA %d\n", oldcapa);
    214 
    215     // try swap
    216     // int rl = fposr[rsl], rh = fposr[rsh], gl = fgroup[rsl], gh = fgroup[rsh];
    217     // printf("swap servers %d %d\n", rsl, rsh);
    218     // printf("swap rows %d %d\n", rl, rh);
    219     // printf("capas on rows are %d %d\n", gcapa[rl][gl], gcapa[rh][gh]);
    220     // printf("their groups are: %d %d\n", fgroup[rsl], fgroup[rsh]);
    221     // printf("their capas are: %d %d\n", oserv[rsl].c, oserv[rsh].c);
    222     // printf("their sizes are: %d %d\n", oserv[rsl].z, oserv[rsh].z);
    223 
    224     // do swap
    225     int tmp;
    226     swap(rsl, rsh);
    227     swap(rsl2, rsh2);
    228 
    229     int nwg = gapas(thefguar);
    230     int newcapa = thefguar[nwg];
    231 
    232     printf("GCAPA is now: %d\n", newcapa);
    233 
    234     if (newcapa >= oldcapa) {
    235       if (newcapa > oldcapa) {
    236         printf("WOOT\n");
    237   for (int i= 0 ; i < M; i++) {
    238     if (fposr[i] >= 0)
    239       printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]);
    240     else
    241       printf("x\n");
    242   }
    243   exit(0);
    244       }
    245       printf("KEEEEEP\n");
    246       continue;
    247     }
    248 
    249     // rollback
    250     swap(rsh, rsl);
    251     swap(rsh2, rsl2);
    252   }
    253     
    254   int fguar[MAXN];
    255   for (int j = 0; j < P; j++)
    256     fguar[j] = capa[j];
    257   for (int j = 0; j < R; j++)
    258     for (int k = 0; k < P; k++)
    259       fguar[k] = min(fguar[k], capa[k] - gcapa[j][k]);
    260   int mfguar = fguar[0];
    261   int idx = 0;
    262   for (int j = 0; j < P; j++)
    263     if (fguar[j] < mfguar) {
    264       mfguar = fguar[j];
    265       idx = j;
    266     }
    267 
    268   printf("best %d placed %d\n", besttcapa, ftcapa);
    269   for (int i = 0; i < P; i++)
    270     printf("guar for %d: %d\n", i, fguar[i]);
    271   printf("FINAL: %d\n", mfguar);
    272   
    273   for (int i = 0; i < R; i++) {
    274     for (int j = 0; j < S; j++)
    275       putchar(grid[i][j] == 1? 'X' : (grid[i][j] == 2 ? 'O' : ' '));
    276     putchar('\n');
    277   }
    278 
    279   printf("CUT\n");
    280 
    281   // display sol
    282   for (int i= 0 ; i < M; i++) {
    283     if (fposr[i] >= 0)
    284       printf("%d %d %d\n", fposr[i], fposc[i], fgroup[i]);
    285     else
    286       printf("x\n");
    287   }
    288 
    289   return 0;
    290 }
    291