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