QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #54480 | #3308. Remote Control | AllenKING_RED | TL | 2ms | 3716kb | C++ | 2.2kb | 2022-10-08 21:45:08 | 2022-10-08 21:45:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,Q;
int nowx,nowy;
map<pair<int,int>,int>q;
string s;
struct mem{
int x;
int y;
}a[N],b[N];
int fa[N];
int find(int x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
cin>>s;
cin>>Q;
for(int i=1;i<=Q;i++)
{
cin>>a[i].x>>a[i].y;
b[i].x=a[i].x;
b[i].y=a[i].y;
fa[i]=i;
if(!q[make_pair(a[i].x,a[i].y)])
q[make_pair(a[i].x,a[i].y)]=i;
else
fa[i]=q[make_pair(a[i].x,a[i].y)];
}
for(int i=0;i<n;i++)
{
if(s[i]=='R')
nowx--;
else if(s[i]=='L')
nowx++;
else if(s[i]=='D')
nowy++;
else if(s[i]=='U')
nowy--;
if(q[make_pair(nowx,nowy)])
{
int num=q[make_pair(nowx,nowy)];
if(s[i]=='R')
{
b[num].x--;
if(!q[make_pair(nowx-1,nowy)])
{
q[make_pair(nowx-1,nowy)]=q[make_pair(nowx,nowy)];
q[make_pair(nowx,nowy)]=0;
}
else
{
fa[find(num)]=find(q[make_pair(nowx-1,nowy)]);
q[make_pair(nowx,nowy)]=0;
}
}
else if(s[i]=='L')
{
b[num].x++;
if(!q[make_pair(nowx+1,nowy)])
{
q[make_pair(nowx+1,nowy)]=q[make_pair(nowx,nowy)];
q[make_pair(nowx,nowy)]=0;
}
else
{
fa[find(num)]=find(q[make_pair(nowx+1,nowy)]);
q[make_pair(nowx,nowy)]=0;
}
}
else if(s[i]=='D')
{
b[num].y++;
if(!q[make_pair(nowx,nowy+1)])
{
q[make_pair(nowx,nowy+1)]=q[make_pair(nowx,nowy)];
q[make_pair(nowx,nowy)]=0;
}
else
{
fa[find(num)]=find(q[make_pair(nowx,nowy+1)]);
q[make_pair(nowx,nowy)]=0;
}
}
else if(s[i]=='U')
{
b[num].y--;
if(!q[make_pair(nowx,nowy-1)])
{
q[make_pair(nowx,nowy-1)]=q[make_pair(nowx,nowy)];
q[make_pair(nowx,nowy)]=0;
}
else
{
fa[find(num)]=find(q[make_pair(nowx,nowy-1)]);
q[make_pair(nowx,nowy)]=0;
}
}
}
}
for(int i=1;i<=Q;i++)
{
int nxt=find(i);
int x=0,y=0;
x=-(nowx-b[nxt].x);
y=-(nowy-b[nxt].y);
cout<<x<<" "<<y<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3628kb
input:
8 RRDRUULL 5 -2 1 -2 2 -2 -1 -3 -1 1 1
output:
-1 3 -1 3 1 0 -2 -1 2 2
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
8 LLDDRRUU 18 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
output:
1 1 -1 2 1 3 2 3 2 3 2 3 3 1 3 2 3 3 1 1 -1 2 1 3 2 3 2 3 2 3 3 1 3 2 3 3
result:
ok 18 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
1000 ULRULRURDDDLURUURULUDRDDRDLURRRUDDDDDURURUDDDRLLDURDDDLLDLULUURDRRDDDURDDRLRULDLUULDLRDLURUUUUDDRULDRRUDDDDUUULLURDUUUULDLDDUUUDUUUUDDLURLUDDDUDLDLRRUDURDRDLRURLUULDRLRDRDDRDRRDLUUURURLRLDUDLDLRURLURUDRRULDRDDRUDDDRURDRRDLDLRDLRDUDDLLLLRUULRRUDURUUUDDDLRDRDRDRURUDDURUDLRLDLLDDULURDURDLLLUULLDLD...
output:
-105 -4 17 -30 41 80 6 -100 23 28 10 -58 -22 -34 1 24 -46 -79 -43 87 -102 -76 85 25 -42 -3 -71 36 -55 -109 -39 -105 5 -102 82 15 42 -22 81 63 -64 -7 -82 -62 74 9 -41 37 21 18 -109 -38 51 48 10 -46 -37 28 -18 -110 -67 -74 -96 -55 -5 16 -49 -21 -81 -56 -106 27 62 48 21 59 -79 72 4 29 17 -65 87 44 72 1...
result:
ok 1000 lines
Test #4:
score: -100
Time Limit Exceeded
input:
300000 DDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURULDDLURU...
output:
1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1...