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

680195.cpp (5390B)


      1 #include <vector>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <map>
      5 #include <time.h>
      6 
      7 using namespace std;
      8 
      9 #define MAXR 77
     10 #define MAXC 302
     11 #define MAXL 2252
     12 #define MAXA 10
     13 #define MAXT 402
     14 #define MAXB 55
     15 
     16 int R, C, A;
     17 int L, V, B, T;
     18 int rs, cs;
     19 
     20 struct Pt{
     21   int r, c;
     22   Pt(int r=0, int c=0) : r(r), c(c) {}
     23 };
     24 
     25 vector<int> coverage[MAXR][MAXC]; // which targets are covered in r c
     26 
     27 Pt dest[MAXA][MAXR][MAXC]; // where does the wind take us: -1 -1 = out
     28 
     29 Pt target[MAXL];
     30 
     31 bool covered[MAXT][MAXL]; // does someone cover target l at time t
     32 
     33 int solution[MAXT][MAXB];
     34 
     35 // for dynamic
     36 int tab[MAXT][MAXA][MAXR][MAXC];
     37 int dir[MAXT][MAXA][MAXR][MAXC];
     38 
     39 int columndist(int c1, int c2) {
     40   return min(abs(c1 - c2), C - abs(c1 - c2));
     41 }
     42 
     43 int iscovered(int l, int r, int c) {
     44   // does a loon at r c cover l?
     45   int u = target[l].r, v = target[l].c;
     46   return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V);
     47 }
     48 
     49 
     50 void calccoverage() {
     51   // compute for each square which targets are covered
     52   for (int r = 0; r < R; r++)
     53     for (int c = 0; c < C; c++)
     54       for (int l = 0; l < L; l++)
     55         if (iscovered(l, r, c))
     56           coverage[r][c].push_back(l);
     57 }
     58 
     59 int chooseda(int b, int t, int a, int r, int c) {
     60   int best = 0, bestda;
     61   if (a == 0)
     62     bestda = 1;
     63   if (a == 1)
     64     bestda = rand() % 2;
     65   if (a == A)
     66     bestda = (rand() % 2) - 1;
     67   if (a > 1 && a < A) {
     68     bestda = (rand() % 3) - 1;
     69   }
     70   for (int da = -1; da <= 1; da++) {
     71     if (a <= 1 && da == -1)
     72       continue; // don't go back down or go down on ground
     73     if (a + da > A)
     74       continue; // can't go too high
     75 
     76     // compute improvement
     77     Pt next = dest[a + da][r][c];
     78     int cscore = 0;
     79     // loons on ground and loons out don't help
     80     if (a + da > 0 && next.r >= 0) {
     81       for (unsigned int i = 0; i < coverage[next.r][next.c].size(); i++) {
     82         int l = coverage[next.r][next.c][i];
     83         cscore += covered[t+1][l] ? 0 : 1;
     84       }
     85     }
     86     if (next.r < 0) {
     87       // out is BAD
     88       cscore = -1;
     89     }
     90     if (cscore > best) {
     91       best = cscore;
     92       bestda = da;
     93     }
     94   }
     95   printf("best da is %d with score %d\n", bestda, best);
     96   return bestda;
     97 }
     98 
     99 int main(int argc, char **argv) {
    100   srand(42);
    101   scanf("%d%d%d", &R, &C, &A);
    102   scanf("%d%d%d%d", &L, &V, &B, &T);
    103   scanf("%d%d", &rs, &cs);
    104   for (int l = 0; l < L; l++) {
    105     int r, c;
    106     scanf("%d%d", &r, &c);
    107     target[l] = Pt(r, c);
    108   }
    109   for (int r = 0; r < R; r++)
    110     for (int c = 0; c < C; c++) {
    111       dest[0][r][c] = Pt(r, c);
    112     }
    113   for (int a = 1; a <= A; a++)
    114     for (int r = 0; r < R; r++)
    115       for (int c = 0; c < C; c++) {
    116         int dr, dc;
    117         scanf("%d%d", &dr, &dc);
    118         int destr, destc;
    119         destr = r + dr;
    120         destc = (c + dc + C) % C;
    121         if (destr < 0 || destr >= R)
    122           destr = destc = -1; // out
    123         dest[a][r][c] = Pt(destr, destc);
    124       }
    125   calccoverage();
    126   //for (int r = 0; r < R; r++) {
    127   //  for (int c = 0; c < C; c++)
    128   //    printf("%d ", (int) coverage[r][c].size());
    129   //  printf("\n");
    130   //}
    131 
    132   int totscore = 0;
    133 
    134   for (int b = 0; b < B; b++) {
    135     // planify loon b
    136     for (int t = 0; t < T; t++)
    137       for (int a = 0; a <= A; a++)
    138         for (int r = 0; r < R; r++)
    139           for (int c = 0; c < C; c++)
    140             tab[t][a][r][c] = dir[t][a][r][c] = 0;
    141     for (int t = T-1; t >= 0; t--) {
    142       if (!(t % 50))
    143         printf("loon %d time %d\n", b, t);
    144       for (int a = 0; a <= A; a++)
    145         for (int r = 0; r < R; r++)
    146           for (int c = 0; c < C; c++) {
    147             int bestda = 0, best = 0;
    148             for (int da = -1; da <= 1; da++) {
    149               if (a <= 1 && da < 0)
    150                 continue;
    151               if (a + da > A)
    152                 continue;
    153               Pt next = dest[a + da][r][c];
    154               if (next.r < 0)
    155                 break;
    156               int cscore = 0;
    157               if (a + da > 0 && next.r >= 0) {
    158                 for (unsigned int i = 0; i < coverage[next.r][next.c].size(); i++) {
    159                   int l = coverage[next.r][next.c][i];
    160                   cscore += covered[t+1][l] ? 0 : 1;
    161                 }
    162               }
    163               int rscore = cscore + tab[t+1][a+da][next.r][next.c];
    164               if (rscore > best) {
    165                 best = rscore;
    166                 bestda = da;
    167               }
    168             }
    169             tab[t][a][r][c] = best;
    170             dir[t][a][r][c] = bestda;
    171           }
    172     }
    173     // ok now follow the best
    174     int r = rs, c = cs, a = 0;
    175     for (int t = 0; t < T; t++) {
    176       printf("loon %d at time %d is %d %d %d\n", b, t, a, r, c);
    177       int bestda = dir[t][a][r][c];
    178       printf("i choose %d\n", bestda);
    179       // ok, apply bestda
    180       a += bestda;
    181       solution[t][b] = bestda;
    182       Pt next = dest[a][r][c];
    183       r = next.r;
    184       c = next.c;
    185       if (r < 0) {
    186         printf("FAILLL\n");
    187         break; // loon is out
    188       }
    189       if (a > 0 && r >= 0) {
    190         // update covered targets
    191         printf("coverage %d %d\n", r, c);
    192         for (unsigned int i = 0; i < coverage[r][c].size(); i++) {
    193           int l = coverage[r][c][i];
    194           totscore += covered[t+1][l] ? 0 : 1;
    195           covered[t+1][l] = true;
    196         }
    197       }
    198     }
    199   }
    200 
    201   // print solution
    202   printf("score %d\n", totscore);
    203 
    204   for (int t = 0; t < T; t++) {
    205     for (int b = 0; b < B; b++)
    206       printf("%d ", solution[t][b]);
    207     printf("\n");
    208   }
    209     
    210   return 0;
    211 }
    212 
    213