修改后100分 感谢大佬 @Suzuki.的修正
https://www.acwing.com/file_system/file/content/whole/index/content/11489223/#comment_627770
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<vector>
#include<stack>
using namespace std;
typedef long long LL;
int n,m,p,q;
pair<LL,LL> pos[100005];
unordered_map<LL,map<int,int>> row;
unordered_map<LL,map<int,int>> col;
unordered_map<LL,map<int,int>> dg;
unordered_map<LL,map<int,int>> udg;
void turn(LL X,LL Y,LL &x,LL &y,LL dis,int t)
{
if(t==0) return;
if(x==X)
{
if(y>Y) x-=dis;
else if(y<Y) x+=dis;
}
else if(y==Y)
{
if(x<X) y-=dis;
else if(x>X) y+=dis;
}
else if(x>X)
{
if(y>Y) x-=dis;
else if(y<Y) y+=dis;
}
else if(x<X)
{
if(y<Y) x+=dis;
else if(y>Y) y-=dis;
}
turn(X,Y,x,y,dis,t-1);
}
int main()
{
cin>>n>>m>>p>>q;
for(int i=1;i<=p;i++)
{
LL x,y;
cin>>x>>y;
pos[i]={x,y};
row[x][y]=i;
col[y][x]=i;
dg[x+y][x]=i;
udg[x-y][x]=i;
}
while(q--)
{
LL X,Y,t;
cin>>X>>Y>>t;
LL k=1e9+5,k2;
LL k2_1=min(X-1,n-X);
LL k2_2=min(Y-1,m-Y);
k2=min(k2_1,k2_2);
vector<int> point;
auto p1=row[X].lower_bound(Y);
if(p1!=row[X].begin())
{
p1--;
k=min(k,abs(Y-p1->first));
point.push_back(p1->second);
}
auto p2=row[X].upper_bound(Y);
if(p2!=row[X].end())
{
k=min(k,abs(Y-p2->first));
point.push_back(p2->second);
}
auto p3=col[Y].lower_bound(X);
if(p3!=col[Y].begin())
{
p3--;
k=min(k,abs(X-p3->first));
point.push_back(p3->second);
}
auto p4=col[Y].upper_bound(X);
if(p4!=col[Y].end())
{
k=min(k,abs(X-p4->first));
point.push_back(p4->second);
}
auto p5=dg[X+Y].lower_bound(X);
if(p5!=dg[X+Y].begin())
{
p5--;
k=min(k,abs(X-p5->first));
point.push_back(p5->second);
}
auto p6=dg[X+Y].upper_bound(X);
if(p6!=dg[X+Y].end())
{
k=min(k,abs(X-p6->first));
point.push_back(p6->second);
}
auto p7=udg[X-Y].lower_bound(X);
if(p7!=udg[X-Y].begin())
{
p7--;
k=min(k,abs(X-p7->first));
point.push_back(p7->second);
}
auto p8=udg[X-Y].upper_bound(X);
if(p8!=udg[X-Y].end())
{
k=min(k,abs(X-p8->first));
point.push_back(p8->second);
}
//cout<<k<<endl;
if(point.size()==0) continue;
if(k>k2) continue;
for(auto e:point)
{
int dis=max(abs(pos[e].first-X),abs(pos[e].second-Y));
if(dis==k)
{
LL &t_x=pos[e].first;
LL &t_y=pos[e].second;
row[t_x].erase(t_y);
col[t_y].erase(t_x);
dg[t_x+t_y].erase(t_x);
udg[t_x-t_y].erase(t_x);
}
}
for(auto e:point)
{
int dis=max(abs(pos[e].first-X),abs(pos[e].second-Y));
if(dis==k)
{
LL &t_x=pos[e].first;
LL &t_y=pos[e].second;
turn(X,Y,t_x,t_y,k,t);
row[t_x][t_y]=e;
col[t_y][t_x]=e;
dg[t_x+t_y][t_x]=e;
udg[t_x-t_y][t_x]=e;
}
}
}
LL ans=1*pos[1].first+pos[1].second;
for(int i=2;i<=p;i++)
{
LL temp=i*pos[i].first+pos[i].second;
ans^=temp;
}
cout<<ans;
return 0;
}
用了二分不超时了但只过部分(35分)
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<vector>
#include<stack>
using namespace std;
typedef long long LL;
int n,m,p,q;
pair<LL,LL> pos[100005];
unordered_map<LL,map<int,int>> row;
unordered_map<LL,map<int,int>> col;
unordered_map<LL,map<int,int>> dg;
unordered_map<LL,map<int,int>> udg;
void turn(LL X,LL Y,LL &x,LL &y,LL dis,int t)
{
if(t==0) return;
if(x==X)
{
if(y>Y) x-=dis;
else if(y<Y) x+=dis;
}
else if(y==Y)
{
if(x<X) y-=dis;
else if(x>X) y+=dis;
}
else if(x>X)
{
if(y>Y) x-=dis;
else if(y<Y) y+=dis;
}
else if(x<X)
{
if(y<Y) x+=dis;
else if(y>Y) y-=dis;
}
turn(X,Y,x,y,dis,t-1);
}
int main()
{
cin>>n>>m>>p>>q;
for(int i=1;i<=p;i++)
{
LL x,y;
cin>>x>>y;
pos[i]={x,y};
row[x][y]=i;
col[y][x]=i;
dg[x+y][x]=i;
udg[x-y][x]=i;
}
// for(int i=1;i<=p;i++)
// {
// printf("%d:(%d,%d)\n",i,pos[i].first,pos[i].second);
// }
while(q--)
{
LL X,Y,t;
cin>>X>>Y>>t;
LL k=1e9+5,k2;
LL k2_1=min(X-1,n-X);
LL k2_2=min(Y-1,m-Y);
k2=min(k2_1,k2_2);
vector<int> point;
auto p1=row[X].lower_bound(Y);
if(p1!=row[X].begin())
{
p1--;
k=min(k,abs(Y-p1->first));
point.push_back(p1->second);
}
auto p2=row[X].upper_bound(Y);
if(p2!=row[X].end())
{
k=min(k,abs(Y-p2->first));
point.push_back(p2->second);
}
auto p3=col[Y].lower_bound(X);
if(p3!=col[Y].begin())
{
p3--;
k=min(k,abs(X-p3->first));
point.push_back(p3->second);
}
auto p4=col[Y].upper_bound(X);
if(p4!=col[Y].end())
{
k=min(k,abs(X-p4->first));
point.push_back(p4->second);
}
auto p5=dg[X+Y].lower_bound(X);
if(p5!=dg[X+Y].begin())
{
p5--;
k=min(k,abs(X-p5->first));
point.push_back(p5->second);
}
auto p6=dg[X+Y].upper_bound(X);
if(p6!=dg[X+Y].end())
{
k=min(k,abs(X-p6->first));
point.push_back(p6->second);
}
auto p7=udg[X-Y].lower_bound(X);
if(p7!=udg[X-Y].begin())
{
p7--;
k=min(k,abs(X-p7->first));
point.push_back(p7->second);
}
auto p8=udg[X-Y].upper_bound(X);
if(p8!=udg[X-Y].end())
{
k=min(k,abs(X-p8->first));
point.push_back(p8->second);
}
//cout<<k<<endl;
if(point.size()==0) continue;
if(k>k2) continue;
for(auto e:point)
{
int dis=max(abs(pos[e].first-X),abs(pos[e].second-Y));
if(dis==k)
{
//cout<<e<<" ";
LL &t_x=pos[e].first;
LL &t_y=pos[e].second;
row[t_x].erase(t_y);
col[t_y].erase(t_x);
dg[t_x+t_y].erase(t_x);
udg[t_x-t_y].erase(t_x);
turn(X,Y,t_x,t_y,k,t);
row[t_x][t_y]=e;
col[t_y][t_x]=e;
dg[t_x+t_y][t_x]=e;
udg[t_x-t_y][t_x]=e;
}
}
}
// for(int i=1;i<=p;i++)
// {
// printf("%d:(%d,%d)\n",i,pos[i].first,pos[i].second);
// }
LL ans=1*pos[1].first+pos[1].second;
for(int i=2;i<=p;i++)
{
LL temp=i*pos[i].first+pos[i].second;
ans^=temp;
}
cout<<ans;
return 0;
}
/*
7 7 9 1
4 4
4 6
3 6
2 6
6 2
2 4
7 4
7 1
4 1
4 4 1
*/
正确但超时得用二分
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<vector>
#include<stack>
using namespace std;
typedef long long LL;
int n,m,p,q;
pair<LL,LL> pos[100005];
map<pair<LL,LL>,int> maze;
int dirx[]={0,1,1,1,0,-1,-1,-1};
int diry[]={1,1,0,-1,-1,-1,0,1};
void turn(LL X,LL Y,LL &x,LL &y,LL dis,int t)
{
if(t==0) return;
if(x==X)
{
if(y>Y) x-=dis;
else if(y<Y) x+=dis;
}
else if(y==Y)
{
if(x<X) y-=dis;
else if(x>X) y+=dis;
}
else if(x>X)
{
if(y>Y) x-=dis;
else if(y<Y) y+=dis;
}
else if(x<X)
{
if(y<Y) x+=dis;
else if(y>Y) y-=dis;
}
turn(X,Y,x,y,dis,t-1);
}
vector<int> bfs(int x,int y,int cnt)
{
vector<int> res;
for(int i=0;i<8;i++)
{
int X=x,Y=y,t=cnt;
while(X>0&&X<=n&&Y>0&&Y<=m&&t--)
{
X+=dirx[i];
Y+=diry[i];
if(maze[{X,Y}])
{
res.push_back(maze[{X,Y}]);
break;
}
}
}
return res;
}
int main()
{
cin>>n>>m>>p>>q;
for(int i=1;i<=p;i++)
{
LL x,y;
cin>>x>>y;
pos[i]={x,y};
maze[{x,y}]=i;
}
// for(int i=1;i<=p;i++)
// {
// printf("%d:(%d,%d)\n",i,pos[i].first,pos[i].second);
// }
while(q--)
{
LL X,Y,t;
cin>>X>>Y>>t;
LL k=1e9+5,k2,flag=0;
LL k2_1=min(X-1,n-X);
LL k2_2=min(Y-1,m-Y);
k2=min(k2_1,k2_2);
vector<int> point = bfs(X,Y,k2);
if(point.size()==0) continue;
for(auto e:point) k= min(k,max(abs(pos[e].first-X),abs(pos[e].second-Y)));
vector<int> temp;
for(auto e:point)
{
int dis=max(abs(pos[e].first-X),abs(pos[e].second-Y));
if(dis==k)
{
maze[{pos[e].first,pos[e].second}]=0;
turn(X,Y,pos[e].first,pos[e].second,k,t);
temp.push_back(e);
}
}
for(auto e:temp) maze[{pos[e].first,pos[e].second}]=e;
//cout<<k;
}
// for(int i=1;i<=p;i++)
// {
// printf("%d:(%d,%d)\n",i,pos[i].first,pos[i].second);
// }
LL ans=1*pos[1].first+pos[1].second;
for(int i=2;i<=p;i++)
{
LL temp=i*pos[i].first+pos[i].second;
ans^=temp;
}
cout<<ans;
return 0;
}
/*
7 7 9 1
4 4
4 6
3 6
2 6
6 2
2 4
7 4
7 1
4 1
*/