# 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

680886.cpp (4545B)

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 int left[MAXT][MAXR][MAXC]; // how many left to cover?
33
34 int solution[MAXT][MAXB];
35
36 // for dynamic
37 int tab[MAXT][MAXA][MAXR][MAXC];
38 int dir[MAXT][MAXA][MAXR][MAXC];
39
40 int columndist(int c1, int c2) {
41   return min(abs(c1 - c2), C - abs(c1 - c2));
42 }
43
44 int iscovered(int l, int r, int c) {
45   // does a loon at r c cover l?
46   int u = target[l].r, v = target[l].c;
47   return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V);
48 }
49
50
51 void calccoverage() {
52   // compute for each square which targets are covered
53   for (int r = 0; r < R; r++)
54     for (int c = 0; c < C; c++)
55       for (int l = 0; l < L; l++)
56         if (iscovered(l, r, c))
57           coverage[r][c].push_back(l);
58 }
59
60 int main(int argc, char **argv) {
61   scanf("%d%d%d", &R, &C, &A);
62   scanf("%d%d%d%d", &L, &V, &B, &T);
63   scanf("%d%d", &rs, &cs);
64   for (int l = 0; l < L; l++) {
65     int r, c;
66     scanf("%d%d", &r, &c);
67     target[l] = Pt(r, c);
68   }
69   for (int r = 0; r < R; r++)
70     for (int c = 0; c < C; c++) {
71       dest[0][r][c] = Pt(r, c);
72     }
73   for (int a = 1; a <= A; a++)
74     for (int r = 0; r < R; r++)
75       for (int c = 0; c < C; c++) {
76         int dr, dc;
77         scanf("%d%d", &dr, &dc);
78         int destr, destc;
79         destr = r + dr;
80         destc = (c + dc + C) % C;
81         if (destr < 0 || destr >= R)
82           destr = destc = -1; // out
83         dest[a][r][c] = Pt(destr, destc);
84       }
85   calccoverage();
86   //for (int r = 0; r < R; r++) {
87   //  for (int c = 0; c < C; c++)
88   //    printf("%d ", (int) coverage[r][c].size());
89   //  printf("\n");
90   //}
91
92   int totscore = 0;
93
94   for (int b = 0; b < B; b++) {
95     // compute left
96     for (int t = 0; t <= T; t++)
97       for (int r = 0; r < R; r++)
98         for (int c = 0; c < C; c++) {
99           int cscore = 0;
100           for (unsigned int i = 0; i < coverage[r][c].size(); i++) {
101             int l = coverage[r][c][i];
102             cscore += covered[t][l] ? 0 : 1;
103           }
104           left[t][r][c] = cscore;
105         }
106     // planify loon b, t == T is sentinel
107     for (int t = 0; t <= T; t++)
108       for (int a = 0; a <= A; a++)
109         for (int r = 0; r < R; r++)
110           for (int c = 0; c < C; c++)
111             tab[t][a][r][c] = dir[t][a][r][c] = 0;
112     for (int t = T-1; t >= 0; t--) {
113       for (int a = 0; a <= A; a++)
114         for (int r = 0; r < R; r++)
115           for (int c = 0; c < C; c++) {
116             int bestda = 0, best = 0;
117             for (int da = -1; da <= 1; da++) {
118               if (a <= 1 && da < 0)
119                 continue;
120               if (a + da > A)
121                 continue;
122               Pt next = dest[a + da][r][c];
123               if (next.r < 0)
124                 break;
125               int rscore = ((a + da) > 0 ? left[t+1][next.r][next.c] : 0) +
126                 tab[t+1][a+da][next.r][next.c];
127               if (rscore > best || (rscore == best && da > bestda)) {
128                 best = rscore;
129                 bestda = da;
130               }
131             }
132             tab[t][a][r][c] = best;
133             dir[t][a][r][c] = bestda;
134           }
135     }
136     // ok now follow the best
137     int r = rs, c = cs, a = 0;
138     for (int t = 0; t < T; t++) {
139       printf("loon %d at time %d is %d %d %d\n", b, t, a, r, c);
140       int bestda = dir[t][a][r][c];
141       printf("i choose %d\n", bestda);
142       // ok, apply bestda
143       a += bestda;
144       solution[t][b] = bestda;
145       Pt next = dest[a][r][c];
146       r = next.r;
147       c = next.c;
148       if (r < 0) {
149         printf("FAILLL\n");
150         break; // loon is out
151       }
152       if (a > 0 && r >= 0) {
153         // update covered targets
154         printf("coverage %d %d\n", r, c);
155         for (unsigned int i = 0; i < coverage[r][c].size(); i++) {
156           int l = coverage[r][c][i];
157           totscore += covered[t+1][l] ? 0 : 1;
158           covered[t+1][l] = true;
159         }
160       }
161     }
162   }
163
164   // print solution
165   printf("score %d\n", totscore);
166
167   for (int t = 0; t < T; t++) {
168     for (int b = 0; b < B; b++)
169       printf("%d ", solution[t][b]);
170     printf("\n");
171   }
172
173   return 0;
174 }
175
176