QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54041#1296. Game DesignBaltinicAC ✓3ms3856kbC++3.5kb2022-10-06 17:42:152022-10-06 17:42:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 17:42:18]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3856kb
  • [2022-10-06 17:42:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 60;
char s[maxn];
int n;
vector<pair<int,int> > blocks;
const int STEPP = 1000;
int STEP =1000;
inline int get_step(){
    return STEP + rand() % 15;
}
pair<int,int> get_nxt(pair<int,int> now,char ori){
    if (ori == 'L'){
        pair<int,int> nxt = make_pair(-0x3f3f3f3f,now.second);
        for (pair<int,int> b : blocks){
            if (b.second == now.second && b.first < now.first){
                nxt.first = max(nxt.first,b.first+ 1);
            }
        }
        return nxt;
    }else if (ori == 'R'){
        pair<int,int> nxt = make_pair(0x3f3f3f3f,now.second);
        for (pair<int,int> b : blocks){
            if (b.second == now.second && b.first > now.first){
                nxt.first = min(nxt.first,b.first- 1);
            }
        }
        return nxt;
    }else if (ori == 'U'){
        pair<int,int> nxt = make_pair(now.first,0x3f3f3f3f);
        for (pair<int,int> b : blocks){
            if (b.first == now.first && b.second > now.second){
                //cout<<"here" << b.first<<","<<b.second<<endl;
                nxt.second = min(nxt.second,b.second - 1);
            }
        }
        return nxt;
    }else if (ori == 'D'){
        pair<int,int> nxt = make_pair(now.first,-0x3f3f3f3f);
        for (pair<int,int> b : blocks){
            if (b.first == now.first && b.second < now.second){
                nxt.second = max(nxt.second,b.second + 1);
            }
        }
        return nxt;
    }else assert(0);
}
bool ok(pair<int,int> start_pos){
    return true;
}
bool check(){
    STEP = STEPP;
    blocks.clear();
    pair<int,int> now = make_pair(0,0);
    for (int i=0;i<n;i++){
        //cout<<"now = "<<now.first <<","<<now.second<<endl;
        pair<int,int> nxt = now;
        if (s[i] == 'L'){
            nxt.first -= get_step();
        }else if (s[i] == 'R'){
            nxt.first += get_step();
        }else if (s[i] == 'U'){
            nxt.second += get_step();
        }else if (s[i] == 'D'){
            nxt.second -= get_step();
        }else assert(0);
        //cout<<"add "<<nxt.first<<","<<nxt.second<<endl;
        blocks.push_back(nxt);
        now = get_nxt(now,s[i]);
        
        STEP += STEPP * 2;
    }
    if (ok(make_pair(0,0))){
        //for (pair<int,int> b : blocks){
        //    printf("[debug] %d %d\n",b.first,b.second);
        //}
        //cout<<now.first<<" "<<now.second<<endl;
        pair<int,int> endpos = blocks.back();
        blocks.pop_back();
        printf("%d %d\n",-endpos.first,-endpos.second);
        printf("%d\n",blocks.size());
        for (pair<int,int> b : blocks){
//            printf("[debug] %d %d\n",b.first,b.second);
            printf("%d %d\n",b.first - endpos.first,b.second - endpos.second);
        }
        return true;
    }
    return false;
}
char get_op(char ori){
    if (ori =='L')return 'R';
    if (ori == 'R')return 'L';
    if (ori == 'U')return 'D';
    if (ori == 'D')return 'U';
    assert(0);
}
int main(){
    scanf("%s",s);
    n = strlen(s);
    if (n >= 3){
        if (s[n-1] == s[n-3] && s[n-2] == get_op(s[n-1])){
            puts("impossible");
            return 0;
        }
    }
    for (int i=1;i<n;i++){
        if (s[i] == s[i-1]){
            puts("impossible");
            return 0;
        }
    }
    for (int i=0;i<100;i++){
        if (check())return 0;
    }

    puts("impossible");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3704kb

input:

LRULR

output:

-3987 -5011
4
-5000 -5011
-1998 -5011
-1999 1
-9009 0

result:

ok 

Test #2:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

DUD

output:

impossible

result:

ok 

Test #3:

score: 0
Accepted
time: 2ms
memory: 3620kb

input:

LRUDLRUDU

output:

impossible

result:

ok 

Test #4:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

UD

output:

0 1989
1
0 3002

result:

ok 

Test #5:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

UDLRUDLRUDLRUDLRUDLR

output:

-10002 9987
19
-10002 11000
-10002 7998
-15014 7999
-8003 7999
-8004 17007
-8004 5996
-21005 5997
-5992 5997
-5993 23006
-5993 4004
-26995 4005
-3987 4005
-3988 29010
-3988 2005
-32996 2006
-1994 2006
-1995 35006
-1995 -1
-39002 0

result:

ok 

Test #6:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

DRULDRULDRULDRULDRUL

output:

20010 -19995
19
20010 -21008
23011 -21007
23010 -15995
16000 -15996
16001 -25004
27011 -25003
27010 -12002
11998 -12003
11999 -29012
31000 -29011
30999 -8009
7992 -8010
7993 -33015
34997 -33014
34996 -4006
3995 -4007
3996 -37007
39002 -37006
39001 1

result:

ok 

Test #7:

score: 0
Accepted
time: 2ms
memory: 3736kb

input:

DRULURDRULURDRULURD

output:

-57025 -38010
18
-57025 -39023
-54024 -39022
-54025 -34010
-61035 -34011
-61034 -25003
-50024 -25004
-50025 -38005
-35013 -38004
-35014 -20995
-54015 -20996
-54014 6
-31007 5
-31008 -25000
-4004 -24999
-4005 4009
-35006 4008
-35005 37008
1 37007

result:

ok 

Test #8:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

RLRLRLRLRLRLRLRLRLRU

output:

-1012 -39001
19
1 -39001
-3001 -39001
2012 -39001
-7010 -39001
6008 -39001
-11010 -39001
10001 -39001
-15012 -39001
14009 -39001
-19001 -39001
18002 -39001
-23007 -39001
22005 -39001
-27004 -39001
26008 -39001
-31001 -39001
30000 -39001
-35006 -39001
34007 -39001

result:

ok 

Test #9:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

DLRDLRDLRDLRDLRDLRD

output:

-12025 133032
18
-12025 132019
-15026 132020
-10013 132020
-10014 125010
-19022 125011
-8011 125011
-8012 112010
-23024 112011
-6014 112011
-6015 93010
-27017 93011
-4009 93011
-4010 68006
-31014 68007
-2005 68007
-2006 37006
-35006 37007
1 37007

result:

ok 

Test #10:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

LULULULULULULULULUL

output:

190056 -171043
18
189043 -171043
189044 -168042
184032 -168043
184033 -161033
175025 -161034
175026 -150024
162025 -150025
162026 -135013
145017 -135014
145018 -116013
124016 -116014
124017 -93007
99012 -93008
99013 -66004
70005 -66005
70006 -35004
37006 -35005
37007 1

result:

ok 

Test #11:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

DRDRDRDRDRURURURURUR

output:

-210044 -99979
19
-210044 -100992
-207043 -100991
-207044 -106003
-200034 -106002
-200035 -115010
-189025 -115009
-189026 -128010
-174014 -128009
-174015 -145018
-155014 -145017
-155015 -124015
-132008 -124016
-132009 -99011
-105005 -99012
-105006 -70004
-74005 -70005
-74006 -37005
-39000 -37006
-39...

result:

ok 

Test #12:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

ULDRDRDRDRDRDRDRLRU

output:

-130038 81019
18
-130038 82032
-133039 82031
-133038 77019
-126028 77020
-126029 68012
-115019 68013
-115020 55012
-100008 55013
-100009 38004
-81008 38005
-81009 17003
-58002 17004
-58003 -8001
-30999 -8000
-31000 -37008
1 -37007
-33000 -37007
2007 -37007

result:

ok 

Test #13:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

URDLRLULRULRULRDLRU

output:

-4003 -59012
18
-4003 -57999
-1002 -58000
-1003 -63012
-8013 -63011
996 -63011
-10015 -63011
-8012 -50010
-23024 -50011
-6014 -50011
-6015 -31010
-27017 -31011
-4009 -31011
-4010 -6006
-31014 -6007
-2005 -6007
-2006 -37008
-35006 -37007
1 -37007

result:

ok 

Test #14:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

DRDRDRLULULUDRDRDRL

output:

-26010 45023
18
-26010 44010
-23009 44011
-23010 38999
-16000 39000
-16001 29992
-4991 29993
-17993 29993
-17992 45005
-35001 45004
-35000 64005
-56002 64004
-56001 87011
-56001 62005
-28997 62006
-28998 32998
2003 32999
2002 -1
37008 0

result:

ok 

Test #15:

score: 0
Accepted
time: 2ms
memory: 3636kb

input:

LR

output:

-1989 0
1
-3002 0

result:

ok 

Test #16:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

L

output:

1013 0
0

result:

ok 

Test #17:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

R

output:

-1013 0
0

result:

ok 

Test #18:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

LURDRULRLRLRLRLRLRU

output:

-15017 -44007
18
-16030 -44007
-16029 -41006
-11017 -41007
-11018 -48017
-2010 -48016
-2011 -37006
-15012 -37007
1 -37007
-17009 -37007
3990 -37007
-21002 -37007
7996 -37007
-25005 -37007
11993 -37007
-29008 -37007
15990 -37007
-33000 -37007
19995 -37007

result:

ok 

Test #19:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

D

output:

0 1013
0

result:

ok 

Test #20:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

RDRUDLRDUDURDULRLUDL

output:

36988 3003
19
38001 3003
38000 2
43012 3
43011 7013
43011 -1996
32001 -1995
45003 -1995
45002 -17007
45002 3
45002 -18999
45002 3996
68009 2
68008 -25003
68008 2002
39000 2001
70002 2001
37001 2001
39001 37007
39001 -1

result:

ok 

Test #21:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

U

output:

0 -1013
0

result:

ok 

Test #22:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

LULRDRLULDR

output:

-2989 9996
10
-4002 9996
-4001 12997
-9013 12996
-2002 12996
-2003 3988
9007 3989
-3995 3989
-3994 19001
-21003 19000
-21002 -1

result:

ok 

Test #23:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

LRULDUDLURUDRDRLUDR

output:

-58986 18002
18
-59999 18002
-56997 18002
-56998 23014
-64008 23013
-64007 14005
-64007 25016
-64007 12014
-79019 14006
-79018 31015
-60017 31014
-60018 52016
-60018 29008
-35013 29009
-35014 2005
-6006 2006
-37008 2006
-37007 35006
-37007 -1

result:

ok 

Test #24:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

LRLDRUDRU

output:

-23006 -8009
8
-24019 -8009
-21017 -8009
-26030 -8009
-24018 -15019
-15010 -15018
-15011 -4008
-15011 -17010
1 -17009

result:

ok 

Test #25:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

RURDRDLDLDL

output:

35980 49029
10
36993 49029
36992 52030
42004 52029
42003 45019
51011 45020
51010 34010
38009 34011
38010 18999
21001 19000
21002 -1

result:

ok 

Test #26:

score: 0
Accepted
time: 2ms
memory: 3808kb

input:

LD

output:

1012 3001
1
-1 3001

result:

ok 

Test #27:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

DRDL

output:

4010 6023
3
4010 5010
7011 5011
7010 -1

result:

ok 

Test #28:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

DRURULULDURURUL

output:

-986 -78007
14
-986 -79020
2015 -79019
2014 -74007
9024 -74008
9023 -65000
-1987 -65001
-1986 -52000
-16998 -52001
-16997 -69010
-16997 -50008
4005 -50009
4004 -27002
29009 -27003
29008 1

result:

ok 

Test #29:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

URLUDULD

output:

15011 6991
7
15011 8004
18012 8003
12999 8003
13000 15013
13000 6004
13000 17015
-1 15012

result:

ok 

Test #30:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

RDRULDULRDRDUR

output:

-47018 11002
13
-46005 11002
-46006 8001
-40994 8002
-40995 15012
-50003 15011
-50002 4001
-50002 17003
-65014 17002
-48004 17002
-48005 -1999
-27003 -1998
-27004 -25005
-27004 1

result:

ok 

Test #31:

score: 0
Accepted
time: 1ms
memory: 3768kb

input:

DUDLUDUDRLDRL

output:

11000 24015
12
11000 23002
11000 26004
11000 20991
3990 23003
3991 32011
3991 21000
3991 34002
3991 16998
21000 21001
1998 21001
1999 -1
25006 0

result:

ok 

Test #32:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

DLURURU

output:

-15018 -26007
6
-15018 -27020
-18019 -27019
-18018 -22007
-11008 -22008
-11009 -13000
1 -13001

result:

ok 

Test #33:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

RLUDUDRDLRDLRDLURLDL

output:

55012 71019
19
56025 71019
53023 71019
53024 76031
53024 69020
53024 78029
53024 65020
66025 69021
66024 54009
49015 54010
68017 54010
68016 33008
45009 33009
70015 33009
70014 6005
41006 6006
41007 37007
74007 37006
39000 37006
39001 -1

result:

ok 

Test #34:

score: 0
Accepted
time: 3ms
memory: 3700kb

input:

ULUDLRLULD

output:

29015 4976
9
29015 5989
26014 5988
26015 11000
26015 3989
17007 3990
28018 3990
15016 3990
17008 19002
-1 19001

result:

ok 

Test #35:

score: 0
Accepted
time: 3ms
memory: 3644kb

input:

RDLRL

output:

impossible

result:

ok 

Test #36:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

RURDULDLRURDRU

output:

-43016 -14996
13
-42003 -14996
-42004 -11995
-36992 -11996
-36993 -19006
-36993 -9997
-48003 -9998
-48002 -22999
-63014 -22998
-46004 -22998
-46005 -3997
-25003 -3998
-25004 -27005
1 -27004

result:

ok 

Test #37:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

RLDLU

output:

8997 -3997
4
10010 -3997
7008 -3997
7009 -9009
-1 -9008

result:

ok 

Test #38:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

URDRLD

output:

-1002 15009
5
-1002 16022
1999 16021
1998 11009
9008 11010
-1 11010

result:

ok 

Test #39:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

DRLDUDRLDULRURDUL

output:

8014 -20968
16
8014 -21981
11015 -21980
6002 -21980
6003 -28990
6003 -19981
6003 -30992
19004 -28989
3991 -28989
3992 -45998
3992 -26996
-17010 -26997
5998 -26997
5997 -1992
33001 -1993
33000 -31001
33000 1

result:

ok 

Test #40:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

RDUDUDRDRUDUR

output:

-56025 -989
12
-55012 -989
-55013 -3990
-55013 1023
-55013 -5988
-55013 5019
-55013 -9988
-42012 -3989
-42013 -19001
-25004 -19000
-25005 1
-25005 -21002
-25005 2006

result:

ok 

Test #41:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

DRDRDRDRDRDRDRDRDRDR

output:

-210044 190055
19
-210044 189042
-207043 189043
-207044 184031
-200034 184032
-200035 175024
-189025 175025
-189026 162024
-174014 162025
-174015 145016
-155014 145017
-155015 124015
-132008 124016
-132009 99011
-105005 99012
-105006 70004
-74005 70005
-74006 37005
-39000 37006
-39001 -1

result:

ok 

Test #42:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

URDLURD

output:

-7000 7993
6
-7000 9006
-3999 9005
-4000 3993
-11010 3994
-11009 13002
1 13001

result:

ok 

Test #43:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

ULURDRDRLURDURDLDRLR

output:

impossible

result:

ok 

Test #44:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

ULURLDRUDUDLULRDLDUD

output:

impossible

result:

ok 

Test #45:

score: 0
Accepted
time: 2ms
memory: 3728kb

input:

ULDULRURLURDRDLURD

output:

-47002 19005
17
-47002 20018
-50003 20017
-50002 15005
-50002 22016
-59010 22015
-47999 22015
-48000 35016
-32988 35015
-49998 35015
-49997 54016
-28995 54015
-28996 31008
-3991 31009
-3992 4005
-33000 4006
-32999 35007
1 35006

result:

ok 

Test #46:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

DRULDUDRDLURDURULDR

output:

-48023 3021
18
-48023 2008
-45022 2009
-45023 7021
-52033 7020
-52032 -1988
-52032 9023
-52032 -3979
-37020 -1987
-37021 -18996
-56022 -18995
-56021 2007
-33014 2006
-33015 -22999
-33015 4006
-4007 4005
-4008 35006
-37008 35005
-37007 -1

result:

ok 

Test #47:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

UDRLULRDRDLULR

output:

2000 3986
13
2000 4999
2000 1997
7012 1998
1 1998
2 11006
-11008 11005
1994 11005
1993 -4007
19002 -4006
19001 -23007
-2001 -23006
-2000 1
-27005 0

result:

ok