QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54480#3308. Remote ControlAllenKING_REDTL 2ms3716kbC++2.2kb2022-10-08 21:45:082022-10-08 21:45:10

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-08 21:45:10]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3716kb
  • [2022-10-08 21:45:08]
  • 提交

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;
}

詳細信息

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...

result: