CSES - Siperia opettaa 3.0 - Results
Submission details
Task:Robots
Sender:zxc
Submission time:2016-07-29 17:50:37 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#20.45 sdetails
#30.42 sdetails
#40.41 sdetails
#5ACCEPTED0.44 sdetails
#60.42 sdetails
#70.41 sdetails
#80.45 sdetails
#90.40 sdetails
#100.36 sdetails
#110.36 sdetails
#120.40 sdetails
#13ACCEPTED0.45 sdetails
#140.32 sdetails
#150.32 sdetails
#16ACCEPTED0.06 sdetails
#170.12 sdetails
#180.24 sdetails
#190.38 sdetails
#200.38 sdetails
#210.38 sdetails
#220.41 sdetails
#230.44 sdetails
#240.47 sdetails
#250.46 sdetails
#260.42 sdetails
#270.43 sdetails
#280.42 sdetails
#290.42 sdetails
#30ACCEPTED0.43 sdetails
#31ACCEPTED0.44 sdetails
#32ACCEPTED0.41 sdetails
#330.46 sdetails
#340.45 sdetails
#35ACCEPTED0.53 sdetails
#360.46 sdetails
#370.44 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:41:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i = 0; i < cmp.size(); ++i) {
                                ^

Code

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll MN = 3e5+100;
ll start[MN];
ll arr[MN];
ll arr2[MN][4];
pair<ll, ll> t[MN];
pair<ll, ll> pck[MN];
set<pair<ll, ll> > sv[MN];
set<pair<ll, ll> > sh[MN];
char dir[MN];
ll mov[MN][2];
ll ans[MN][2];

map<pair<ll, ll>, int> qwe;
int main() {
    ll n,T;
    cin>>n>>T;
    vector<ll> cmp;
    for(ll i = 0; i < n; ++i) {
	cin>>t[i].F>>t[i].S>>dir[i];
	if(dir[i] == 'U') mov[i][1] = 1;
	if(dir[i] == 'D') mov[i][1] = -1;
	if(dir[i] == 'L') mov[i][0] = -1;
	if(dir[i] == 'R') mov[i][0] = 1;
	cmp.push_back(t[i].F);
	cmp.push_back(t[i].S);
	qwe[{t[i].F, t[i].S}] = i;
	ans[i][0] = t[i].F;
	ans[i][1] = t[i].S;
	start[i] = -1;
	arr[i] = -1;
	for(int j = 0; j < 4; ++j) arr2[i][j] = 2e18;
    }
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    map<ll, ll> mp;
    for(ll i = 0; i < cmp.size(); ++i) {
	mp[cmp[i]] = i;
    }
    for(ll i = 0; i < n; ++i) {
	sv[mp[t[i].F]].insert({mp[t[i].S], i});
	sh[mp[t[i].S]].insert({mp[t[i].F], i});
    }
    set<pair<ll, ll> > qq;
    qq.insert({0, 0});
    start[0] = 0;
    ans[0][0] = t[0].F;
    ans[0][1] = t[0].S;
    ans[0][0] += T * mov[0][0];
    ans[0][1] += T * mov[0][1];
    ll cx = mp[t[0].F];
    ll cy = mp[t[0].S];
    sv[cx].erase({t[0].S, 0});
    sh[cy].erase({t[0].F, 0});
    while(qq.size()) {
	auto p = *qq.begin();
	qq.erase(*qq.begin());
	ll x = t[p.S].F + mov[p.S][0] * (p.F-start[p.S]);
	ll y = t[p.S].S + mov[p.S][1] * (p.F-start[p.S]);
	int c = qwe[{x, y}];
	if(p.F > T) break;
	if(start[c] == -1) {
	    ans[c][0] = t[c].F;
	    ans[c][1] = t[c].S;
	    ans[c][0] += (T-p.F)*mov[c][0];
	    ans[c][1] += (T-p.F)*mov[c][1];

	    start[c] = p.F;
	    qq.insert({p.F, c});
	    ll cx = mp[t[c].F];
	    ll cy = mp[t[c].S];
	    sv[cx].erase({t[c].S, c});
	    sh[cy].erase({t[c].F, c});
	}
	ll px = mp[x];
	ll py = mp[y];
	if(dir[p.S] == 'U') {
	    auto z = sv[px].lower_bound({y, 0});
	    if(z == sv[px].end()) continue;
	    auto z2 = *z;
	    ll time = t[z2.S].S-y + p.F;
	    //cout<<"LOL "<<time<<'\n';
	    if(arr2[z2.S][2] <= time) {
		continue;
	    }
	    arr2[z2.S][2] = time;
	    qq.insert({time, p.S});
	}
	if(dir[p.S] == 'D') {
	    auto z = sv[px].lower_bound({y, 0});
	    if(z == sv[px].begin()) continue;
	    --z;
	    auto z2 = *z;
	    ll time = y-t[z2.S].S + p.F;
	    if(arr2[z2.S][0] <= time) {
		continue;
	    }
	    arr2[z2.S][0] = time;
	    qq.insert({time, p.S});
	}
	if(dir[p.S] == 'R') {
	    auto z = sh[py].lower_bound({x, 0});
	    if(z == sh[py].end()) continue;
	    auto z2 = *z;
	    ll time = t[z2.S].F-x + p.F;
	    if(arr2[z2.S][3] <= time) {
		continue;
	    }
	    arr2[z2.S][3] = time;
	    qq.insert({time, p.S});
	}
	if(dir[p.S] == 'L') {
	    auto z = sh[py].lower_bound({x, 0});
	    if(z == sh[py].begin()) continue;
	    --z;
	    auto z2 = *z;
	    ll time = x - t[z2.S].F + p.F;
	    if(arr2[z2.S][1] <= time) {
		continue;
	    }
	    arr2[z2.S][1] = time;
	    qq.insert({time, p.S});
	}
    }
    for(int i = 0; i < n; ++i) {
	cout<<ans[i][0]<<' '<<ans[i][1]<<'\n';
    }
}

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:

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
158260522 426364560
158260522 759037020
158260522 427764980
158260522 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
795628008 257250937
795628008 550072283
795628008 144321804
795628008 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 258142892
531527275 138986229
531527275 319183722
730349222 3971805
...

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:

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
734315399 37563938
528773362 37563938
...

Test 8

Verdict:

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
386075092 461633934
386075092 124926580
386075092 755378486
386075092 727330147
...

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
393591774 293077924
46211797 40626753
251187352 317219315
882175209 492633736
...

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 989020485
850928761 393946779
983081163 353187253
849295618 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
95402381 -999999999819422752
820355630 869868252
510574002 947140642
107928860 216094009
449664703 741244839
...

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
545737590 -999999999712586770
32300820 112475277
95613327 287413230
631751785 410333678
654111144 662448296
...

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 535170540
257716848 892169727
672216693 273108699
608110094 539410304
...

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
10958668995 246058339
503666498 889608806
366854683 570796148
799588075 970911538
251188854 382210484
...

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 272667868
80707751 128641666
578149194 953490880
591537576 763864532
...

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 756883251
432539187 70051676
974910212 631543164
484550186 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
580124599 603753069
761464601 921205988
238952989 715879557
541559959 639504333
...

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 201116843
5384772 513343753
803303889 722536184
104886651 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 920533064
180614597 177949083
38188492 507979841
463449590 82199217
...

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:

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:

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 961500530
775679740 901490976
775679740 260604449
775679740 93919169
...

Test 25

Verdict:

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 836712760
782906609 242210260
782906609 162010416
782906609 608862474
...

Test 26

Verdict:

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:

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 228308715
744756599 585682143
...

Test 28

Verdict:

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:

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:

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
473921396 711582662
473921396 883086059
473921396 871996608
473921396 241283927
...

Test 34

Verdict:

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
894449066 840501706
894449066 986139460
894449066 892106502
894449066 804680105
...

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:

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
918270168 538029753
918270168 656461613
918270168 846616703
918270168 398233347
...

Test 37

Verdict:

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
382945727 945023696
382945727 920093999
382945727 991771365
382945727 730754030
...