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) {
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
```