CSES - Siperia opettaa 3.0 - Results
Submission details
Task:Robots
Sender:Kuha
Submission time:2016-07-29 15:18:33 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.32 sdetails
#30.34 sdetails
#40.34 sdetails
#5ACCEPTED0.29 sdetails
#6ACCEPTED0.32 sdetails
#70.33 sdetails
#8ACCEPTED0.33 sdetails
#90.36 sdetails
#100.35 sdetails
#110.40 sdetails
#120.41 sdetails
#13ACCEPTED0.30 sdetails
#140.32 sdetails
#150.37 sdetails
#16ACCEPTED0.06 sdetails
#170.10 sdetails
#180.25 sdetails
#190.35 sdetails
#200.37 sdetails
#210.35 sdetails
#220.31 sdetails
#23ACCEPTED0.30 sdetails
#24ACCEPTED0.29 sdetails
#25ACCEPTED0.32 sdetails
#26ACCEPTED0.32 sdetails
#27ACCEPTED0.32 sdetails
#28ACCEPTED0.31 sdetails
#29ACCEPTED0.31 sdetails
#30ACCEPTED0.30 sdetails
#31ACCEPTED0.30 sdetails
#32ACCEPTED0.23 sdetails
#33ACCEPTED0.32 sdetails
#34ACCEPTED0.32 sdetails
#35ACCEPTED0.31 sdetails
#36ACCEPTED0.31 sdetails
#37ACCEPTED0.32 sdetails

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define LINF 999999999999999999LL
#define N (1<<17)
#define M 1000000007

using namespace std;

ll x[100001];
ll y[100001];
char d[100001];
ll at[100001];

ll dist (int a, int b) {
  return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}

int main () {
  set<pair<pair<int, int>, int>> xs;
  set<pair<pair<int, int>, int>> ys;
  int n;
  ll t;
  cin>>n>>t;
  for (int i = 1; i <= n; i++) {
    cin>>x[i]>>y[i]>>d[i];
    at[i] = t;
    if (i > 1) xs.insert({{x[i], y[i]}, i});
    if (i > 1) ys.insert({{y[i], x[i]}, i});
  }
  dist(2, 5);
  at[1] = 0;
  priority_queue<pair<ll, int>> v;
  v.push({0, 1});
  
  while (!v.empty()) {
    if (xs.size() == 0) break;
    int i = v.top().second;
    ll tm = -v.top().first;
    v.pop();
    vector<set<pair<pair<int, int>, int>>::iterator> ex;
    vector<set<pair<pair<int, int>, int>>::iterator> ey;
    if (d[i] == 'U') {
      auto p = xs.lower_bound({{x[i], y[i]}, 0});
      while (p != xs.end() && (*p).first.first == x[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ex.push_back(p);
	++p;
      }
    }
    if (d[i] == 'D') {
      auto p = xs.upper_bound({{x[i], y[i]}, 0});
      p--;
      while (p != (--xs.begin()) && (*p).first.first == x[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ex.push_back(p);
	--p;
      }
    }
    if (d[i] == 'R') {
      auto p = ys.lower_bound({{y[i], x[i]}, 0});
      while (p != ys.end() && (*p).first.first == y[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ey.push_back(p);
	++p;
      }
    }
    if (d[i] == 'L') {
      auto p = ys.upper_bound({{y[i], x[i]}, 0});
      p--;
      while (p != (--ys.begin()) && (*p).first.first == y[i]) {
	int k = (*p).second;
	if (at[k] == t) {
	  at[k] = dist(i, k) + tm;
	  if (at[k] > INF) at[k] = INF;
	  else v.push({-at[k], k});
	}
	ey.push_back(p);
	--p;
      }
    }
    for (auto a : ex) xs.erase(a);
    for (auto a : ey) ys.erase(a);
  }
  
  for (int i = 1; i <= n; i++) {
    if (d[i] == 'U') cout<<x[i]<<" "<<y[i] + t - at[i]<<endl;
    if (d[i] == 'D') cout<<x[i]<<" "<<y[i] - t + at[i]<<endl;
    if (d[i] == 'L') cout<<x[i] - t + at[i]<<" "<<y[i]<<endl;
    if (d[i] == 'R') cout<<x[i] + t - at[i]<<" "<<y[i]<<endl;
  }
}

Test details

Test 1

Verdict: ACCEPTED

input
5 10
1 0 U
3 1 U
1 2 R
1 1 L
...

correct output
1 10
3 6
9 2
-8 1
8 1

user output
1 10
3 6
9 2
-8 1
8 1

Test 2

Verdict: ACCEPTED

input
100000 1000000000000000000
158260522 833086986 U
158260522 426364560 L
158260522 759037020 R
158260522 427764980 L
...

correct output
158260522 1000000000833086986
-999999999434892416 426364560
1000000000084085920 759037020
-999999999436292836 427764980
-999999999611530938 603003082
...

user output
158260522 1000000000833086986
-999999999434892416 426364560
1000000000084085920 759037020
-999999999436292836 427764980
-999999999611530938 603003082
...

Test 3

Verdict:

input
100000 1000000000000000000
233552954 47283907 D
795628008 257250937 R
795628008 550072283 U
795628008 144321804 R
...

correct output
233552954 -999999999952716093
1000000000023080040 257250937
795628008 999999999484702969
1000000000136009173 144321804
-999999998580742143 108332818
...

user output
233552954 -999999999952716093
1000000000022956612 257250937
795628008 999999999550072284
1000000000136009173 144321804
-999999998580742143 108332818
...

Test 4

Verdict:

input
100000 1000000000000000000
531527275 380312548 L
368745941 258142892 D
531527275 138986229 U
531527275 319183722 R
...

correct output
-999999999468472725 380312548
368745941 -999999998733348866
531527275 999999999174102658
999999999746841197 319183722
730349222 999999999102895757
...

user output
-999999999468472725 380312548
368745941 -999999998741857109
531527275 999999999173316196
999999999746054735 319183722
730349222 999999999102895757
...

Test 5

Verdict: ACCEPTED

input
100000 1000000000000000000
561380534 729502086 D
203720318 729502086 U
813185473 729502086 L
808991828 729502086 L
...

correct output
561380534 -999999999270497914
203720318 729502086
813185473 729502086
808991828 729502086
772433385 729502086
...

user output
561380534 -999999999270497914
203720318 729502086
813185473 729502086
808991828 729502086
772433385 729502086
...

Test 6

Verdict: ACCEPTED

input
100000 1000000000000000000
40633672 256815712 U
392684870 590303299 D
203773372 590303299 L
593293112 590303299 U
...

correct output
40633672 1000000000256815712
392684870 590303299
203773372 590303299
593293112 590303299
652768710 590303299
...

user output
40633672 1000000000256815712
392684870 590303299
203773372 590303299
593293112 590303299
652768710 590303299
...

Test 7

Verdict:

input
100000 1000000000000000000
317153144 37563938 D
461986566 37563938 D
594935002 37563938 U
734315399 37563938 R
...

correct output
317153144 -999999999962436062
461986566 -999999998732505128
594935002 999999998674684568
999999999232055632 37563938
528773362 999999998740846208
...

user output
317153144 -999999999962436062
461986566 37563938
594935002 37563938
999999999734315400 37563938
528773362 37563938
...

Test 8

Verdict: ACCEPTED

input
100000 1000000000000000000
386075092 217120430 U
386075092 461633934 L
386075092 124926580 U
386075092 755378486 L
...

correct output
386075092 1000000000217120430
-999999999369411404 461633934
386075092 1000000000032619042
-999999999075666852 755378486
386075092 1000000000217120430
...

user output
386075092 1000000000217120430
-999999999369411404 461633934
386075092 1000000000032619042
-999999999075666852 755378486
386075092 1000000000217120430
...

Test 9

Verdict:

input
100000 1000000000000000000
812304066 108536522 D
393591774 293077924 R
46211797 40626753 U
251187352 317219315 L
...

correct output
812304066 -999999999891463478
999999999789937222 293077924
46211797 999999999206624715
-999999998978612283 317219315
882175209 1000000000036976417
...

user output
812304066 -999999999891463478
999999999788649118 293077924
46211797 999999999066882429
-999999998977636119 317219315
882175209 1000000000036210493
...

Test 10

Verdict:

input
100000 1000000000000000000
636581665 627517899 U
384326252 989020485 D
850928761 393946779 D
983081163 353187253 L
...

correct output
636581665 1000000000627517899
384326252 -999999998397221516
850928761 -999999999149349241
-999999998387302929 353187253
1000000000175761774 175483772
...

user output
636581665 1000000000627517899
384326252 -999999998397221516
850928761 -999999999145950317
-999999998349140877 353187253
1000000000172862328 175483772
...

Test 11

Verdict:

input
100000 1000000000000000000
95402381 180577248 D
820355630 869868252 L
510574002 947140642 U
107928860 216094009 D
...

correct output
95402381 -999999999819422752
-999999997751978659 869868252
510574002 999999999751984169
107928860 -999999999722441293
999999999521313332 741244839
...

user output
(empty)

Test 12

Verdict:

input
100000 1000000000000000000
545737590 287413230 D
32300820 112475277 U
95613327 287413230 U
631751785 410333678 L
...

correct output
545737590 -999999999712586770
32300820 999999999423128362
95613327 999999999711338923
-999999999034335720 410333678
1000000000045724672 662448296
...

user output
(empty)

Test 13

Verdict: ACCEPTED

input
100000 1000000000000000000
726706648 742813187 U
170991532 742813187 U
245380683 742813187 R
239885395 742813187 L
...

correct output
726706648 1000000000742813187
170991532 742813187
245380683 742813187
239885395 742813187
101591873 742813187
...

user output
726706648 1000000000742813187
170991532 742813187
245380683 742813187
239885395 742813187
101591873 742813187
...

Test 14

Verdict:

input
89153 1000000000
452747846 962556007 L
666044562 535170540 D
257716848 892169727 U
672216693 273108699 R
...

correct output
-547252154 962556007
666044562 176384675
257716848 1626752449
762768586 273108699
608110094 118450207
...

user output
-547252154 962556007
666044562 198343339
257716848 1593120549
760440036 273108699
608110094 120778757
...

Test 15

Verdict:

input
91906 10000000000
958668995 246058339 R
503666498 889608806 U
366854683 570796148 R
799588075 970911538 L
...

correct output
10958668995 246058339
503666498 9776131210
9435377930 570796148
-8301553174 970911538
251188854 9523653566
...

user output
(empty)

Test 16

Verdict: ACCEPTED

input
242 100000000000
203049518 714923922 L
441395303 860719447 R
71823579 316450815 U
743887311 533611458 R
...

correct output
-99796950482 714923922
441395303 860719447
71823579 316450815
743887311 533611458
543109434 456937805
...

user output
-99796950482 714923922
441395303 860719447
71823579 316450815
743887311 533611458
543109434 456937805
...

Test 17

Verdict:

input
24226 1000000000000
285356318 942519123 U
690346553 272667868 D
80707751 128641666 D
578149194 953490880 R
...

correct output
285356318 1000942519123
690346553 -998559928912
80707751 -998787983056
1000116303085 953490880
591537576 1000186466953
...

user output
285356318 1000942519123
690346553 -998727332133
80707751 -998871358335
999791608491 953490880
591537576 1000068689447
...

Test 18

Verdict:

input
67458 10000000000000
818609843 930613401 L
70389372 756883251 U
432539187 70051676 D
974910212 631543164 U
...

correct output
-9999181390157 930613401
70389372 9999834932630
432539187 -9998683315943
974910212 10000133392346
9999371433379 151556251
...

user output
-9999181390157 930613401
70389372 9999832220380
432539187 -9998929948325
974910212 10000133392346
9999484550187 151556251
...

Test 19

Verdict:

input
100000 1000000000000000000
592825996 837436381 U
580124599 603753069 R
761464601 921205988 R
238952989 715879557 U
...

correct output
592825996 1000000000837436381
1000000000306735572 603753069
1000000000509056389 921205988
238952989 1000000000213445408
541559959 -999999999084293264
...

user output
592825996 1000000000837436381
1000000000306735572 603753069
1000000000509056389 921205988
238952989 1000000000184178918
541559959 -999999999007432134
...

Test 20

Verdict:

input
100000 1000000000000000000
666277986 159178888 R
591518992 201116843 D
5384772 513343753 L
803303889 722536184 L
...

correct output
1000000000666277986 159178888
591518992 -999999999579455514
-999999998978305285 513343753
-999999998496312912 722536184
-999999998548487533 943161505
...

user output
1000000000666277986 159178888
591518992 -999999999579455514
-999999998994615229 513343753
-999999998394989342 722536184
-999999998895113350 943161505
...

Test 21

Verdict:

input
100000 1000000000000000000
829714962 808467768 R
964319842 920533064 D
180614597 177949083 U
38188492 507979841 R
...

correct output
1000000000829714962 808467768
964319842 -999999998447796436
180614597 999999998830414811
999999998866360637 507979841
463449590 -999999998642658912
...

user output
1000000000829714962 808467768
964319842 -999999998447796436
180614597 999999999177949084
999999999038188493 507979841
463449590 -999999998917800784
...

Test 22

Verdict:

input
100000 1000000000000000000
952227250 823291392 D
709686642 725165530 D
691423285 213889225 R
200279445 575351813 D
...

correct output
952227250 -999999999176708608
709686642 -999999996980760384
999999996733114765 213889225
200279445 -999999995569031779
-999999995586295722 262801002
...

user output
952227250 -999999999176708608
709686642 725165530
691423285 213889225
200279445 575351813
156994593 262801002
...

Test 23

Verdict: ACCEPTED

input
100000 1000000000000000000
253685402 394065730 L
715663507 323731110 L
635131545 724754972 D
647819839 760698125 L
...

correct output
-999999999746314598 394065730
715663507 323731110
635131545 724754972
647819839 760698125
331875175 123596160
...

user output
-999999999746314598 394065730
715663507 323731110
635131545 724754972
647819839 760698125
331875175 123596160
...

Test 24

Verdict: ACCEPTED

input
100000 1000000000000000000
775679740 954819331 U
775679740 961500530 U
775679740 901490976 U
775679740 260604449 U
...

correct output
775679740 1000000000954819331
775679740 1000000000954819331
775679740 901490976
775679740 260604449
775679740 93919169
...

user output
775679740 1000000000954819331
775679740 1000000000954819331
775679740 901490976
775679740 260604449
775679740 93919169
...

Test 25

Verdict: ACCEPTED

input
100000 1000000000000000000
782906609 133235274 U
782906609 836712760 D
782906609 242210260 U
782906609 162010416 D
...

correct output
782906609 1000000000133235274
782906609 -999999998459809754
782906609 1000000000133235274
782906609 -999999999809214442
782906609 -999999998915510326
...

user output
782906609 1000000000133235274
782906609 -999999998459809754
782906609 1000000000133235274
782906609 -999999999809214442
782906609 -999999998915510326
...

Test 26

Verdict: ACCEPTED

input
100000 1000000000000000000
904492027 527595435 U
904492027 507833832 U
320683452 830672563 U
320683452 723405646 U
...

correct output
904492027 1000000000527595435
904492027 507833832
320683452 830672563
320683452 723405646
320683452 152800852
...

user output
904492027 1000000000527595435
904492027 507833832
320683452 830672563
320683452 723405646
320683452 152800852
...

Test 27

Verdict: ACCEPTED

input
100000 1000000000000000000
940767425 124739249 D
744756599 542257788 D
744756599 141763433 U
940767425 228308715 D
...

correct output
940767425 -999999999875260751
744756599 542257788
744756599 141763433
940767425 -999999999668108125
744756599 585682143
...

user output
940767425 -999999999875260751
744756599 542257788
744756599 141763433
940767425 -999999999668108125
744756599 585682143
...

Test 28

Verdict: ACCEPTED

input
100000 1000000000000000000
397746824 159049030 U
1703392 159049030 U
419939112 159049030 U
835014838 159049030 U
...

correct output
397746824 1000000000159049030
1703392 159049030
419939112 159049030
835014838 159049030
148936277 541749540
...

user output
397746824 1000000000159049030
1703392 159049030
419939112 159049030
835014838 159049030
148936277 541749540
...

Test 29

Verdict: ACCEPTED

input
100000 1000000000000000000
723992675 321471314 U
156254457 528919984 D
733307343 321471314 D
739607186 321471314 U
...

correct output
723992675 1000000000321471314
156254457 528919984
733307343 321471314
739607186 321471314
111573745 321471314
...

user output
723992675 1000000000321471314
156254457 528919984
733307343 321471314
739607186 321471314
111573745 321471314
...

Test 30

Verdict: ACCEPTED

input
100000 1000000000000000000
675407479 250089291 U
451161204 250089291 U
910761092 250089291 U
947320836 250089291 U
...

correct output
675407479 1000000000250089291
451161204 250089291
910761092 250089291
947320836 250089291
833457294 250089291
...

user output
675407479 1000000000250089291
451161204 250089291
910761092 250089291
947320836 250089291
833457294 250089291
...

Test 31

Verdict: ACCEPTED

input
100000 1000000000000000000
196189124 228526447 U
477932095 228526447 D
687059944 228526447 D
326471760 228526447 U
...

correct output
196189124 1000000000228526447
477932095 228526447
687059944 228526447
326471760 228526447
341135829 228526447
...

user output
196189124 1000000000228526447
477932095 228526447
687059944 228526447
326471760 228526447
341135829 228526447
...

Test 32

Verdict: ACCEPTED

input
100000 1000000000
0 100000 D
0 99999 D
0 99998 D
0 99997 D
...

correct output
0 -999900000
0 -999900000
0 -999900000
0 -999900000
0 -999900000
...

user output
0 -999900000
0 -999900000
0 -999900000
0 -999900000
0 -999900000
...

Test 33

Verdict: ACCEPTED

input
100000 1000000000000000000
473921396 890834979 U
473921396 711582662 L
473921396 883086059 D
473921396 871996608 D
...

correct output
473921396 1000000000890834979
-999999999346703263 711582662
473921396 -999999999109041997
473921396 -999999999109041997
-999999998876404528 241283927
...

user output
473921396 1000000000890834979
-999999999346703263 711582662
473921396 -999999999109041997
473921396 -999999999109041997
-999999998876404528 241283927
...

Test 34

Verdict: ACCEPTED

input
100000 1000000000000000000
894449066 575115655 U
894449066 840501706 L
894449066 986139460 L
894449066 892106502 D
...

correct output
894449066 1000000000575115655
-999999998840164883 840501706
-999999998694527129 986139460
894449066 -999999998790902651
894449066 1000000000575115655
...

user output
894449066 1000000000575115655
-999999998840164883 840501706
-999999998694527129 986139460
894449066 -999999998790902651
894449066 1000000000575115655
...

Test 35

Verdict: ACCEPTED

input
100000 1000000000000000000
259474019 781547542 L
211709778 840501706 D
225226213 986139460 R
141335940 892106502 U
...

correct output
-999999999740525981 781547542
211709778 840501706
225226213 986139460
141335940 892106502
242296739 804680105
...

user output
-999999999740525981 781547542
211709778 840501706
225226213 986139460
141335940 892106502
242296739 804680105
...

Test 36

Verdict: ACCEPTED

input
100000 1000000000000000000
918270168 57575548 D
918270168 538029753 R
918270168 656461613 U
918270168 846616703 U
...

correct output
918270168 -999999999942424452
1000000000437623027 538029753
918270168 1000000000057382612
918270168 1000000000057382612
1000000000577419433 398233347
...

user output
918270168 -999999999942424452
1000000000437623027 538029753
918270168 1000000000057382612
918270168 1000000000057382612
1000000000577419433 398233347
...

Test 37

Verdict: ACCEPTED

input
100000 1000000000000000000
382945727 643341572 U
382945727 945023696 R
382945727 920093999 D
382945727 991771365 R
...

correct output
382945727 1000000000643341572
1000000000081263603 945023696
382945727 -999999998803153574
1000000000034515934 991771365
382945727 1000000000643341572
...

user output
382945727 1000000000643341572
1000000000081263603 945023696
382945727 -999999998803153574
1000000000034515934 991771365
382945727 1000000000643341572
...