1
#include <stdio.h>
2
#include <fstream>
3
#include <algorithm>
4
#include <cmath>
5
 
6
static unsigned long long seed = 5;
7
 
8
static int pseudo_rand(void)
9
{
10
    seed = seed * 25214903917ULL + 11ULL;
11
    return (seed >> 16) & 0x3fffffff;
12
}
13
 
14
static const long long PENALTY = 10'000'000'000'000LL;
15
static const int MAX_TC = 1;
16
static const int MAXN = 1000;
17
static const int MAXM = 1000;
18
static const int ROAD_CNT = 100;
19
 
20
static const int UP = 0;
21
static const int RIGHT = 1;
22
static const int DOWN = 2;
23
static const int LEFT = 3;
24
 
25
static const int TURN_LEFT = 3;
26
static const int TURN_RIGHT = 1;
27
static const int GO_STRAIGHT = 0;
28
 
29
static const int UPLEFT = 1;
30
static const int RIGHTUP = 2;
31
static const int DOWNRIGHT = 3;
32
static const int LEFTDOWN = 4;
33
static const int VERTICAL = 5;
34
static const int HORIZONTAL = 6;
35
 
36
struct Coordinates
37
{
38
    int y, x;
39
    Coordinates()
40
    {
41
        y = x = 0;
42
    }
43
    Coordinates(int y_, int x_)
44
    {
45
        y = y_;
46
        x = x_;
47
    }
48
};
49
 
50
struct TrafficSignal
51
{
52
    int signal, next_signal;
53
    TrafficSignal()
54
    {
55
        signal = next_signal = 0;
56
    }
57
};
58
 
59
struct Vehicle
60
{
61
    int x, y, dir, dest_y, dest_x;
62
};
63
 
64
static Coordinates src[ROAD_CNT*2], dest[ROAD_CNT*2];
65
static int map[MAXN][MAXM], crossroad_id[MAXN][MAXM];
66
static TrafficSignal signal_list[ROAD_CNT*ROAD_CNT];
67
static Vehicle vehicles[MAXN];
68
static int vehicle_on_map[MAXN][MAXM];
69
static int is_movable[MAXN];
70
static int turn_dir[MAXN];
71
static int K, L;
72
 
73
static int map_bak[MAXN][MAXM], crossroad_id_bak[MAXN][MAXM];
74
static Vehicle vehicles_bak[MAXN];
75
 
76
int dy[4] = {-1, 0, 1, 0};
77
int dx[4] = {0, 1, 0, -1};
78
 
79
static int min_x, min_y, max_x, max_y;
80
 
81
void change_signal(int cross_id, int next_signal)
82
{
83
    if (next_signal <= 0 || next_signal > 6) return;
84
    signal_list[cross_id].signal = 0;
85
    signal_list[cross_id].next_signal = next_signal;
86
}
87
 
88
static void make_tc() {
89
    K = 0, L = 0;
90
    min_y = MAXN-1, max_y = 0;
91
    min_x = MAXM-1, max_x = 0;
92
    for (int y = 0; y < MAXM; y++)
93
    {
94
        for (int x = 0; x < MAXM; x++)
95
        {
96
            crossroad_id[y][x] = 0;
97
            map[y][x] = 0;
98
        }
99
    }
100
 
101
    for (int i = 0; i < ROAD_CNT; i++)
102
    {
103
        int dir = pseudo_rand() % 2;
104
        if (dir == 0)
105
        {
106
            int y = pseudo_rand() % (MAXM - 200) + 100;
107
            if(map[y-1][0] == 1 || map[y][0] == 1 || map[y+1][0] == 1 || map[y+2][0] == 1) continue;
108
 
109
            for (int x = 0; x < MAXM; x++)
110
            {
111
                map[y][x] = map[y + 1][x] = 1;
112
            }
113
            src[K] = Coordinates(y + 1, 0);
114
            dest[K++] = Coordinates(y, 0);
115
            src[K] = Coordinates(y, MAXM - 1);
116
            dest[K++] = Coordinates(y + 1, MAXM - 1);
117
            if (min_y > y) min_y = y;
118
            if (max_y < y) max_y = y;
119
        }
120
        // Similar for vertical roads
121
        else
122
        {
123
            int x = pseudo_rand() % (MAXM - 200) + 100;
124
            if(map[0][x-1] == 1 || map[0][x] == 1 || map[0][x+1] == 1 || map[0][x+2] == 1)
125
                continue;
126
            for (int y = 0; y < MAXM; y++)
127
            {
128
                map[y][x] = map[y][x + 1] = 1;
129
            }
130
            src[K] = Coordinates(0, x);
131
            dest[K++] = Coordinates(0, x+1);
132
            src[K] = Coordinates(MAXM - 1, x+1);
133
            dest[K++] = Coordinates(MAXM - 1, x);
134
            if (min_x > x) min_x = x;
135
            if (max_x < x) max_x = x;
136
        }
137
    }
138
 
139
    L = 0;
140
    for (int y = 100; y < MAXM - 100; y++)
141
    {
142
        if (map[y - 1][0] == 0 && map[y][0] == 1)
143
        {
144
            for (int x = 100; x < MAXM-100; x++)
145
            {
146
                if (map[y-1][x] == 1 && map[y-1][x-1] == 0)
147
                {
148
                    L++;
149
                    crossroad_id[y][x] = crossroad_id[y+1][x] = crossroad_id[y][x+1] = crossroad_id[y+1][x+1] = L; 
150
                    signal_list[L].signal = signal_list[L].next_signal = 1;
151
                }
152
            }
153
        }
154
    }
155
 
156
    for (int i = MAXN - 1; i >= 0; i--)
157
    {
158
        int src_idx = 0, dest_idx = 0;
159
        do {
160
            src_idx = pseudo_rand() % K;
161
            dest_idx = pseudo_rand() % K;
162
        } while (src_idx == dest_idx);
163
        vehicles[i].y = src[src_idx].y;
164
        vehicles[i].x = src[src_idx].x;
165
        vehicles[i].dest_y = dest[dest_idx].y;
166
        vehicles[i].dest_x = dest[dest_idx].x;
167
        if(vehicles[i].y < 100)
168
        {
169
            src[src_idx].y++;
170
            vehicles[i].dir = DOWN;
171
        }
172
        else if(vehicles[i].y >= MAXM - 100)
173
        {
174
            src[src_idx].y--;
175
            vehicles[i].dir = UP;
176
        }
177
        else if(vehicles[i].x < 100)
178
        {
179
            src[src_idx].x++;
180
            vehicles[i].dir = RIGHT;
181
        }
182
        else if(vehicles[i].x >= MAXM - 100)
183
        {
184
            src[src_idx].x--;
185
            vehicles[i].dir = LEFT;
186
        }
187
    }
188
    for(int y = 0; y < MAXN; y++)
189
    {
190
        for(int x = 0; x < MAXM; x++)
191
        {
192
            vehicle_on_map[y][x] = 0;
193
            map_bak[y][x] = map[y][x];
194
            crossroad_id_bak[y][x] = crossroad_id[y][x];
195
        }
196
    }
197
 
198
    for(int i = 0; i < MAXN; i++)
199
    {
200
        vehicles_bak[i] = vehicles[i];
201
        vehicle_on_map[vehicles[i].y][vehicles[i].x] = 1;
202
    }
203
}
204
 
205
static int get_nextdir(Vehicle& tar)
206
{
207
    int dir = tar.dir;
208
    int y = tar.y;
209
    int x = tar.x;
210
    int dest_y = tar.dest_y;
211
    int dest_x = tar.dest_x;
212
    int next_y = y + dy[dir];
213
    int next_x = x + dx[dir];
214
    if(dest_y < next_y - 1)
215
    {
216
        if(dest_x < next_x - 1)
217
        {
218
            if(dir == RIGHT)
219
            {
220
                return TURN_LEFT;
221
            }
222
            else if(dir == DOWN)
223
            {
224
                return TURN_RIGHT;
225
            }
226
            else if(dir == UP)
227
            {
228
                if(next_y <= min_y + 1)
229
                {
230
                    return TURN_LEFT;
231
                }
232
            }
233
            else if(dir == LEFT)
234
            {
235
                if(next_x <= min_x + 1)
236
                {
237
                    return TURN_RIGHT;
238
                }
239
            }
240
        }
241
        else if(dest_x > next_x + 1)
242
        {
243
            if(dir == RIGHT)
244
            {
245
                if(next_x > max_x - 1)
246
                {
247
                    return TURN_LEFT;
248
                }
249
            }
250
            else if(dir == DOWN)
251
            {
252
                return TURN_LEFT;
253
            }
254
            else if(dir == UP)
255
            {
256
                if(next_y <= min_y + 1)
257
                {
258
                    return TURN_RIGHT;
259
                }
260
            }
261
            else if(dir == LEFT)
262
            {
263
                return TURN_RIGHT;
264
            }
265
        }
266
        else
267
        {
268
            if(dir == RIGHT)
269
            {
270
                return TURN_LEFT;
271
            }
272
            else if(dir == LEFT)
273
            {
274
                return TURN_RIGHT;
275
            }
276
        }
277
    }
278
    else if(dest_y > next_y + 1)
279
    {
280
        if(dest_x < next_x - 1)
281
        {
282
            if(dir == RIGHT)
283
            {
284
                return TURN_RIGHT;
285
            }
286
            else if(dir == DOWN)
287
            {
288
                if(next_y > max_y - 1)
289
                {
290
                    return TURN_RIGHT;
291
                }
292
            }
293
            else if(dir == UP)
294
            {
295
                return TURN_LEFT;
296
            }
297
            else if(dir == LEFT)
298
            {
299
                if(next_x <= min_x + 1)
300
                {
301
                    return TURN_LEFT;
302
                }
303
            }
304
        }
305
        else if(dest_x > next_x + 1)
306
        {
307
            if(dir == RIGHT)
308
            {
309
                if(next_x > max_x - 1)
310
                {
311
                    return TURN_RIGHT;
312
                }
313
            }
314
            else if(dir == DOWN)
315
            {
316
                if(next_y > max_y - 1)
317
                {
318
                    return TURN_LEFT;
319
                }
320
            }
321
            else if(dir == UP)
322
            {
323
                return TURN_RIGHT;
324
            }
325
            else if(dir == LEFT)
326
            {
327
                return TURN_LEFT;
328
            }
329
        }
330
        else
331
        {
332
            if(dir == RIGHT)
333
            {
334
                return TURN_RIGHT;
335
            }
336
            else if(dir == LEFT)
337
            {
338
                return TURN_LEFT;
339
            }
340
        }
341
    }
342
    else
343
    {
344
        if(dest_x < next_x - 1)
345
        {
346
            if(dir == UP)
347
            {
348
                return TURN_LEFT;
349
            }
350
            else if(dir == DOWN)
351
            {
352
                return TURN_RIGHT;
353
            }
354
        }
355
        else if(dest_x > next_x + 1)
356
        {
357
            if(dir == UP)
358
            {
359
                return TURN_RIGHT;
360
            }
361
            else if(dir == DOWN)
362
            {
363
                return TURN_LEFT;
364
            }
365
        }
366
    }
367
    return GO_STRAIGHT;
368
}
369
 
370
void move_vehicles() {
371
    for(int i = 0; i < MAXN; i++)
372
    {
373
        is_movable[i] = 0;
374
    }
375
 
376
    for (int i = 0; i < MAXN; i++)
377
    {
378
        int x = vehicles[i].x;
379
        int y = vehicles[i].y;
380
        int dir = vehicles[i].dir;
381
        int next_x = x + dx[dir];
382
        int next_y = y + dy[dir];
383
 
384
        if(vehicles[i].dest_x == x && vehicles[i].dest_y == y)
385
        {
386
            continue;
387
        }
388
 
389
        if(vehicle_on_map[next_y][next_x] == 1)
390
        {
391
            continue;
392
        }
393
 
394
        if(crossroad_id[next_y][next_x] == 0)
395
        {
396
            is_movable[i] = 1;
397
        }
398
        else
399
        {
400
            if(crossroad_id[y][x] == 0)
401
            {
402
                int signal = signal_list[crossroad_id[next_y][next_x]].signal;
403
                turn_dir[i] = get_nextdir(vehicles[i]);
404
                if(turn_dir[i] == TURN_RIGHT)
405
                {
406
                    is_movable[i] = 1;
407
                }
408
                else
409
                {
410
                    if(dir == UP && signal == UPLEFT)
411
                    {
412
                        is_movable[i] = 1;
413
                    }
414
                    else if(dir == RIGHT && signal == RIGHTUP)
415
                    {
416
                        is_movable[i] = 1;
417
                    }
418
                    else if(dir == DOWN && signal == DOWNRIGHT)
419
                    {
420
                        is_movable[i] = 1;
421
                    }
422
                    else if(dir == LEFT && signal == LEFTDOWN)
423
                    {
424
                        is_movable[i] = 1;
425
                    }
426
 
427
                    if(turn_dir[i] == GO_STRAIGHT)
428
                    {
429
                        if(dir == UP || dir == DOWN)
430
                        {
431
                            if(signal == VERTICAL)
432
                            {
433
                                is_movable[i] = 1;
434
                            }
435
                        }
436
                        else
437
                        {
438
                            if(signal == HORIZONTAL)
439
                            {
440
                                is_movable[i] = 1;
441
                            }
442
                        }
443
                    }
444
                }
445
            }
446
            else
447
            {
448
                is_movable[i] = 1;
449
            }
450
        }
451
 
452
    }
453
 
454
    for (int i = 0; i < MAXN; i++) {
455
        if (!is_movable[i]) continue;
456
 
457
        int x = vehicles[i].x;
458
        int y = vehicles[i].y;
459
        int dir = vehicles[i].dir;
460
        int next_x = x + dx[dir];
461
        int next_y = y + dy[dir];
462
 
463
        if (vehicle_on_map[next_y][next_x] == 0)
464
        {
465
            vehicle_on_map[y][x] = 0;
466
            vehicle_on_map[next_y][next_x] = 1;
467
            vehicles[i].x = next_x;
468
            vehicles[i].y = next_y;
469
            
470
            if(turn_dir[i] == TURN_RIGHT)
471
            {
472
                vehicles[i].dir = (dir + 1) % 4;
473
                turn_dir[i] = GO_STRAIGHT;
474
            }
475
            else if(turn_dir[i] == TURN_LEFT)
476
            {
477
                int next_dir = (dir + 3) % 4;
478
                if(next_dir == UP)
479
                {
480
                    if(map[next_y + 1][next_x + 1] == 0)
481
                    {
482
                        vehicles[i].dir = next_dir;
483
                        turn_dir[i] = GO_STRAIGHT;
484
                    }
485
                }
486
                else if(next_dir == RIGHT)
487
                {
488
                    if(map[next_y + 1][next_x - 1] == 0)
489
                    {
490
                        vehicles[i].dir = next_dir;
491
                        turn_dir[i] = GO_STRAIGHT;
492
                    }
493
                }
494
                else if(next_dir == DOWN)
495
                {
496
                    if(map[next_y - 1][next_x - 1] == 0)
497
                    {
498
                        vehicles[i].dir = next_dir;
499
                        turn_dir[i] = GO_STRAIGHT;
500
                    }
501
                }
502
                else if(next_dir == LEFT)
503
                {
504
                    if(map[next_y - 1][next_x + 1] == 0)
505
                    {
506
                        vehicles[i].dir = next_dir;
507
                        turn_dir[i] = GO_STRAIGHT;
508
                    }
509
                }
510
            }
511
 
512
            // Check if the vehicle has reached its destination
513
            if (vehicles[i].x == vehicles[i].dest_x && vehicles[i].y == vehicles[i].dest_y) {
514
                vehicle_on_map[vehicles[i].y][vehicles[i].x] = 0;
515
            }
516
        }
517
    }
518
 
519
    // Update signals for crossroads
520
    for(int i = 0; i < L; i++)
521
    {
522
        signal_list[i].signal = signal_list[i].next_signal;
523
    }
524
}
525
 
526
bool verify()
527
{
528
    for(int i = 0; i < MAXN; i++)
529
    {
530
        if(vehicles[i].x != vehicles[i].dest_x || vehicles[i].y != vehicles[i].dest_y)
531
        {
532
            return false;
533
        }
534
    }
535
    return true;
536
}
537
 
538
extern void init(int N, int map[][MAXM], int crossroad_id[][MAXM], Vehicle vehicles[MAXN]);
539
extern bool process();
540
 
541
int main()
542
{
543
    long long gTotalScore = 0;
544
    for(int i = 0; i < MAX_TC; i++)
545
    {
546
        make_tc();
547
        std::ofstream game_state_file("game_state.txt");
548
        if (game_state_file.is_open()) {
549
            game_state_file << "Vehicles:\n";
550
            for (int i = 0; i < MAXN; i++) {
551
                game_state_file << "Vehicle " << i << ": (" << vehicles_bak[i].y << ", " << vehicles_bak[i].x << ") -> ("
552
                                << vehicles_bak[i].dest_y << ", " << vehicles_bak[i].dest_x << "), dir: " << vehicles_bak[i].dir << "\n";
553
            }
554
            game_state_file.close();
555
        } else {
556
            printf("Unable to open file game_state.txt");
557
        }
558
        
559
        init(MAXM, map_bak, crossroad_id_bak, vehicles_bak);
560
 
561
        bool is_finished = false;
562
        
563
        while(is_finished == false)
564
        {
565
            is_finished = process();
566
            move_vehicles();
567
            gTotalScore++;
568
        }
569
 
570
        if(verify() == false)
571
        {
572
            gTotalScore = PENALTY;
573
        }
574
    }
575
 
576
    printf("%lld\n", gTotalScore);
577
}