QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54041 | #1296. Game Design | Baltinic | AC ✓ | 3ms | 3856kb | C++ | 3.5kb | 2022-10-06 17:42:15 | 2022-10-06 17:42:18 |
Judging History
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;
}
详细
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