CSES - APIO 2012 - Results
Submission details
Task:Kunai
Sender:ArktinenKarpalo
Submission time:2019-03-17 17:01:34 +0200
Language:C++
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1, 2, 3details
#2ACCEPTED0.05 s1, 2, 3details
#3ACCEPTED0.04 s1, 2, 3details
#4ACCEPTED0.05 s1, 2, 3details
#5ACCEPTED0.05 s1, 2, 3details
#6ACCEPTED0.03 s1, 2, 3details
#70.02 s2, 3details
#80.02 s2, 3details
#90.02 s2, 3details
#100.01 s2, 3details
#110.02 s2, 3details
#120.02 s2, 3details
#130.02 s2, 3details
#140.01 s2, 3details
#150.02 s2, 3details
#160.03 s2, 3details
#170.03 s2, 3details
#180.02 s2, 3details
#190.03 s2, 3details
#200.03 s2, 3details
#210.02 s2, 3details
#220.03 s3details
#230.02 s3details
#240.01 s3details
#250.03 s3details
#260.02 s3details
#270.01 s3details
#280.02 s3details
#290.02 s3details
#300.02 s3details
#310.01 s3details
#320.03 s3details
#330.02 s3details
#340.02 s3details
#350.01 s3details
#360.01 s3details
#370.01 s3details
#380.02 s3details
#390.01 s3details
#400.02 s3details
#410.02 s3details
#420.01 s3details
#430.02 s3details
#440.01 s3details
#450.01 s3details
#460.01 s3details
#470.01 s3details
#480.02 s3details
#490.01 s3details
#500.03 s3details
#510.02 s3details
#520.02 s3details
#530.01 s3details
#540.02 s3details
#550.01 s3details
#560.01 s3details
#570.01 s3details

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 100000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, w, h, xx[1010], yy[1010], d[1010], rdk[1010][1010], t[1010], pt[1010][1010];

bool oob(int x, int y) {
	if(x < 1 || y < 1 || y > h || x > w)
		return true;
	else
		return false;
}

void t1(int mns) { 
	int x = xx[mns];
	int y = yy[mns];
	int dir = d[mns];
	int xofs = 0;
	int yofs = 0;
	int dd = 0;
	if(dir == 0) { // Right
		xofs = 1;
		dd = 2;
	} else if(dir == 1) { // Up
		yofs = -1;
		dd = 3;
	} else if(dir == 2) { // Left
		xofs = -1;
		dd = 0;
	} else if(dir == 3) { // Down
		yofs = +1;
		dd = 1;
	}
	if(rdk[x+xofs][y+yofs] && d[rdk[x+xofs][y+yofs]] == dd) {
		t[rdk[x][y]] = 1;
		t[rdk[x+xofs][y+yofs]] = 1;
		rdk[x][y] = 0;
		rdk[x+xofs][y+yofs] = 0;
	}
}

vector<pair<int,int>> pois1, pois2; 
void s1(int mns) {
	int x = xx[mns];
	int y = yy[mns];
	int dir = d[mns];
	int xofs = 0;
	int yofs = 0;
	if(dir == 0) { // Right
		xofs = 1;
	} else if(dir == 1) { // Up
		yofs = -1;
	} else if(dir == 2) { // Left
		xofs = -1;
	} else if(dir == 3) { // Down
		yofs = +1;
	}
	xx[mns] += xofs;
	yy[mns] += yofs;
	if(oob(x+xofs, y+yofs)) {
		t[mns] = 1;
		return;
	}
	if(rdk[x+xofs][y+yofs]) {
		int luku = rdk[x+xofs][y+yofs];
		if(luku==1e9) {
			t[mns] = 1;
		} else {
			t[luku] = 1;
			t[mns] = 1;
			rdk[x+xofs][y+yofs] = 1e9;
			pois1.push_back(make_pair(x+xofs, y+yofs));
		}
	} else {
		rdk[x+xofs][y+yofs] = mns;
		pois2.push_back(make_pair(x+xofs, y+yofs));
	}
	pt[x+xofs][y+yofs] = 1;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> w >> h;
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> xx[i] >> yy[i] >> d[i];
		pois2.push_back(make_pair(xx[i], yy[i]));
		pt[xx[i]][yy[i]] = 2+i;
		rdk[xx[i]][yy[i]] = i;
	}
	for(int i=1; i<=1000; i++) {
		for(int j=1; j<=n; j++) {
			if(t[j])
				continue;
			t1(j);
		}
		for(auto u:pois2)
			rdk[u.first][u.second] = 0;
		pois2.clear();
		for(int j=1; j<=n; j++) {
			if(t[j])
				continue;
			s1(j);
		}
		for(auto u:pois1)
			rdk[u.first][u.second] = 0;
		pois1.clear();
	}
	int ans = 0;
	for(int i=1; i<=h; i++) {
		for(int j=1; j<=w; j++) {
			if(pt[j][i])
				ans++;
		}
	}
	cout << ans;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000 1000
1000
395 147 2
312 997 3
575 326 1
...

correct output
351232

user output
351232

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000 1000
1000
613 767 3
847 338 0
65 684 2
...

correct output
341331

user output
341331

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000 1000
1000
545 235 1
751 441 2
393 441 0
...

correct output
2332

user output
2332

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000 1000
1000
508 691 1
88 522 2
594 543 2
...

correct output
91488

user output
91488

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
987 863
1000
337 215 1
426 724 0
314 667 2
...

correct output
304733

user output
304733

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000 1000
1000
134 885 1
99 920 2
853 166 1
...

correct output
50224

user output
50224

Test 7

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
622691628 400169593 1
88321523 864579498 2
112795648 764418241 2
...

correct output
510718011549

user output
(empty)

Test 8

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
434001832 559301213 3
434001832 429662335 3
406314803 401975306 0
...

correct output
2291715446

user output
(empty)

Test 9

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
147530776 854510 0
356276711 182273622 1
892824604 150655760 0
...

correct output
88532373705

user output
(empty)

Test 10

Group: 2, 3

Verdict:

input
987285921 863112267
1000
470324395 497062190 3
442802251 378184556 2
119175366 201807368 0
...

correct output
455873598338

user output
(empty)

Test 11

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
909404004 181534702 2
484518608 606420098 1
218950493 871988213 2
...

correct output
27655301105

user output
(empty)

Test 12

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
773022132 211005023 2
999330973 728414009 3
788418382 315547103 0
...

correct output
481150067104

user output
(empty)

Test 13

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
50373611 409198926 0
450050051 9522486 1
450050051 329920540 1
...

correct output
2849288541

user output
(empty)

Test 14

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
541475743 439195694 1
704685352 411213621 0
541475743 919546919 3
...

correct output
82091697388

user output
(empty)

Test 15

Group: 2, 3

Verdict:

input
987285921 863112267
1000
620654899 592269001 0
206328053 105131334 2
782084021 752936230 2
...

correct output
467023572658

user output
(empty)

Test 16

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
561552965 495764463 2
359727447 697589981 2
465263943 592053485 1
...

correct output
25388296783

user output
(empty)

Test 17

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
589070350 565712291 0
841681509 118453997 3
572166871 967138461 1
...

correct output
508058157318

user output
(empty)

Test 18

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
466098270 174395571 1
708125245 416422546 2
596968012 416422546 2
...

correct output
4246358023

user output
(empty)

Test 19

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
384004974 137019999 3
407193458 545911984 3
402045605 540764131 0
...

correct output
79305870521

user output
(empty)

Test 20

Group: 2, 3

Verdict:

input
987285921 863112267
1000
449417196 662604888 1
48678588 632059056 2
565832510 404527588 0
...

correct output
463406908716

user output
(empty)

Test 21

Group: 2, 3

Verdict:

input
1000000000 1000000000
1000
475820435 547875716 2
167693733 856002418 1
449458888 574237263 1
...

correct output
41055207693

user output
(empty)

Test 22

Group: 3

Verdict:

input
1000000000 1000000000
100000
663138948 732069328 2
335193741 619561225 2
228849515 139776269 1
...

correct output
49941362127608

user output
(empty)

Test 23

Group: 3

Verdict:

input
1000000000 1000000000
100000
566759277 849622939 3
250197041 533060703 0
852403088 533060703 2
...

correct output
39994458607

user output
(empty)

Test 24

Group: 3

Verdict:

input
1000000000 1000000000
100000
856953368 114383681 3
850373774 417536320 2
506532450 913767411 3
...

correct output
8477051419311

user output
(empty)

Test 25

Group: 3

Verdict:

input
987285921 863112267
100000
750078204 431759396 3
735927921 507211726 2
89989784 643673044 3
...

correct output
46150537505050

user output
(empty)

Test 26

Group: 3

Verdict:

input
1027 1039
100000
942 795 2
446 469 1
768 800 0
...

correct output
1054717

user output
(empty)

Test 27

Group: 3

Verdict:

input
1000000000 1000000000
100000
137117336 890747686 1
384041069 643823953 1
29726055 998138967 2
...

correct output
476523338176

user output
(empty)

Test 28

Group: 3

Verdict:

input
1000000000 1000000000
100000
331703518 86776596 3
177544276 9601214 2
12598004 791367628 2
...

correct output
50126205700926

user output
(empty)

Test 29

Group: 3

Verdict:

input
1000000000 1000000000
100000
276411077 540284323 0
435323848 381371552 1
435323848 625003151 3
...

correct output
56095255153

user output
(empty)

Test 30

Group: 3

Verdict:

input
1000000000 1000000000
100000
908028273 567997813 2
572250164 903775922 3
236472055 567997813 0
...

correct output
8253896297688

user output
(empty)

Test 31

Group: 3

Verdict:

input
987285921 863112267
100000
63453291 200913904 1
262979526 382364396 3
428521173 461559387 3
...

correct output
46229727046871

user output
(empty)

Test 32

Group: 3

Verdict:

input
1027 1039
100000
511 323 0
956 419 1
81 48 0
...

correct output
1055185

user output
(empty)

Test 33

Group: 3

Verdict:

input
1000000000 1000000000
100000
657870508 354607304 2
491838553 520639259 1
660690262 351787550 2
...

correct output
507526568312

user output
(empty)

Test 34

Group: 3

Verdict:

input
1000000000 1000000000
100000
147751737 294000216 1
19894811 252157555 2
943830141 442958986 3
...

correct output
49957015480521

user output
(empty)

Test 35

Group: 3

Verdict:

input
1000000000 1000000000
100000
450108760 547507943 0
451372067 546244636 1
315061883 547507943 0
...

correct output
62352343214

user output
(empty)

Test 36

Group: 3

Verdict:

input
1000000000 1000000000
100000
93427566 250549170 3
556201946 314045627 1
655446864 413290545 2
...

correct output
8258222391750

user output
(empty)

Test 37

Group: 3

Verdict:

input
987285921 863112267
100000
706589704 692508905 3
105330061 488033004 3
212269662 113150745 0
...

correct output
46221255626007

user output
(empty)

Test 38

Group: 3

Verdict:

input
1027 1039
100000
746 684 2
99 227 1
880 315 1
...

correct output
1056052

user output
(empty)

Test 39

Group: 3

Verdict:

input
1000000000 1000000000
100000
72121795 956404235 1
977020574 51505456 2
435320669 593205361 1
...

correct output
407410639854

user output
(empty)

Test 40

Group: 3

Verdict:

input
1000000000 1000000000
100000
482034022 897612026 0
941070079 873435725 2
835704386 342496489 0
...

correct output
49919072427797

user output
(empty)

Test 41

Group: 3

Verdict:

input
1000000000 1000000000
100000
519936637 258601371 1
763550477 502215211 2
519936637 745829051 3
...

correct output
44497041760

user output
(empty)

Test 42

Group: 3

Verdict:

input
1000000000 1000000000
100000
487637375 302473543 1
591230757 406066925 2
487637375 509660307 3
...

correct output
8307354131507

user output
(empty)

Test 43

Group: 3

Verdict:

input
987285921 863112267
100000
856920207 366456602 0
856141785 636238896 3
875178317 664279607 2
...

correct output
46179682182549

user output
(empty)

Test 44

Group: 3

Verdict:

input
1027 1039
100000
17 190 3
868 463 2
483 978 3
...

correct output
1056218

user output
(empty)

Test 45

Group: 3

Verdict:

input
1000000000 1000000000
100000
391529494 653705763 1
112895171 932340086 1
69191361 976043896 2
...

correct output
568892059623

user output
(empty)

Test 46

Group: 3

Verdict:

input
1000000000 1000000000
100000
298082241 104835646 2
783420614 115992066 2
619452875 994087848 1
...

correct output
49997496156308

user output
(empty)

Test 47

Group: 3

Verdict:

input
1000000000 1000000000
100000
621949231 509438831 2
535984856 595403206 3
450020481 509438831 0
...

correct output
51467675232

user output
(empty)

Test 48

Group: 3

Verdict:

input
1000000000 1000000000
100000
877374451 447747847 2
537306871 787815427 3
197239291 447747847 0
...

correct output
8314959264748

user output
(empty)

Test 49

Group: 3

Verdict:

input
987285921 863112267
100000
685682505 858051603 1
698492320 741907504 3
658926806 315870965 3
...

correct output
46246375985396

user output
(empty)

Test 50

Group: 3

Verdict:

input
1027 1039
100000
314 212 3
610 176 2
139 78 1
...

correct output
1056041

user output
(empty)

Test 51

Group: 3

Verdict:

input
1000000000 1000000000
100000
900809794 96891967 1
784333884 263748228 2
62490464 985591648 2
...

correct output
442226775128

user output
(empty)

Test 52

Group: 3

Verdict:

input
1000000000 1000000000
100000
114130459 459542914 0
625771149 506032054 2
403201364 645679206 2
...

correct output
50026483129307

user output
(empty)

Test 53

Group: 3

Verdict:

input
1000000000 1000000000
100000
880347982 516662451 2
552033074 844977359 3
223718166 516662451 0
...

correct output
48456523650

user output
(empty)

Test 54

Group: 3

Verdict:

input
1000000000 1000000000
100000
586976368 613454196 3
410434589 436912417 0
586976368 260370638 1
...

correct output
8303589567989

user output
(empty)

Test 55

Group: 3

Verdict:

input
987285921 863112267
100000
170295294 135611110 1
383193391 511391566 3
226423785 40312796 2
...

correct output
46287075850758

user output
(empty)

Test 56

Group: 3

Verdict:

input
1027 1039
100000
612 757 0
352 412 2
823 741 2
...

correct output
1055250

user output
(empty)

Test 57

Group: 3

Verdict:

input
1000000000 1000000000
100000
652150584 446262032 1
811568386 286844230 1
492561855 605850761 1
...

correct output
614169021291

user output
(empty)