[noi simulation] Elis (greedy, simulation)

Topic

$${}_{{}_{1\mathrm{s}512\mathrm{m}\mathrm{b}}}$$

Answer key

We will find that , At any time, the minimum threshold of the magic eye is one of the four corners of the square , Therefore, we only need to consider the magic eyes on the four corners .

It can be greedy to judge whether there is a solution .

Get the scheme with the smallest dictionary order , Try to go right every step + Greedy judge whether there is a solution .

So how to judge greedily ？

notes ： The following is the greedy strategy to judge whether there is a solution , Not the final output answer .

We can partition the whole grid first ： The five pointed star array is the magic eye area

Because the threshold value of magic eye decreases every time is equal to Manhattan distance , Therefore, the general direction must be the closer to the magic eye area, the better .

stay A Regional time , Greedily walked all the way to the lower left corner of the magic eye area , Feel free to go halfway , The effect on the magic eye area is the same .

In the blue arrow area , The closer you get, the better , It must be mindless to go up .

stay B Regional time , It doesn't matter how you go , The effect on the magic eye area is the same .

When you enter the magic eye area , It's going to be a bit of a hassle ,

Suppose you are currently in the magic eye area $(x,y)$ , Walking out of the magic eye area halfway is definitely not good , So it must be all the way to $C$ spot , This is the right way $A,C$ The impact is the same . It's out $C$ After o'clock, I just walk around , So we should try to make $B,D$ The minimum value of the threshold is the maximum .

The plan on the left is right $B$ The most beneficial 、 Yes $D$ The most harmful plan , The plan on the right is the opposite ：

We consider the adjustment method , Adjust from the scheme on the left to the scheme on the right , One at a time “ Up right ” become “ The upper right ”, Will just let $B$ The threshold of 2,$D$ The threshold of is increased 2 . therefore , No matter what plan , Yes $B,D$ The threshold contribution and are equal , The boundary is the above two cases . We can $O(1)$ Greedy distribution , In the end $B,D$ The threshold of is as average as possible .

Code implementation is a simulation problem .

Time complexity $O(n)$ . Since it's a simulation , Constants can be written big .

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#pragma GCC optimize(2)
using namespace std;
#define MAXN (1<<16|5)
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int n,m,s,o,k;
int a,b,c;
LL A_,B_,L_,R_,t;
int Abs(int x) {
    return x<0 ? -x:x;}
int dis(int x,int y,int a,int b) {
    
	return Abs(a-x) + Abs(b-y);
}
LL sm(int l,int r) {
    return (l+r) *1ll* (r-l+1) / 2;}
bool check(int x,int y,LL A,LL B,LL L,LL R) {
    
	if(A > t || B > t || L > t || R > t) return 0;
	if(x == n+1 && y == n) return 1;
	if(x < a)
		return check(a,b,A+sm(1,dis(x,y,a,b)),B+sm(c+c+1,dis(x,y,a+c,b+c)),
		L+sm(c+1,dis(x,y,a,b+c)),R+sm(c+1,dis(x,y,a+c,b)));
	if(x >= a+c && y >= b+c)
		return check(n+1,n,A+sm(x-a+y-b,n-a+n-b),B+sm(x-a-c+y-b-c,n-a-c+n-b-c),
		L+sm(x+y-a-b-c,n+n-a-b-c),R+sm(x+y-a-b-c,n+n-a-b-c));
	if(x <= a+c && y < b)
		return check(x,b,A+sm(x-a+1,dis(x,y,a,b)),B+sm(a+c-x+c+1,dis(x,y,a+c,b+c)),
		L+sm(dis(x,b-1,a,b+c),dis(x,y,a,b+c)),R+sm(a+c-x+1,dis(x,y,a+c,b)));
	if(x > a+c && y < b)
		return check(x,b,A+sm(x-a+1,dis(x,y,a,b)),B+sm(x-a+1,dis(x,y,a,b)),
		L+sm(dis(x,b-1,a,b+c),dis(x,y,a,b+c)),R+sm(x-a-c+1,dis(x,y,a+c,b)));
	if(x > a+c && y < b+c)
		return check(x,b+c,A+sm(dis(x,y,a,b),dis(x,b+c-1,a,b)),B+sm(dis(x,b+c-1,a+c,b+c),dis(x,y,a+c,b+c)),
		L+sm(dis(x,b+c-1,a,b+c),dis(x,y,a,b+c)),R+sm(dis(x,y,a+c,b),dis(x,b+c-1,a+c,b)));
	
	A += sm(dis(x,y,a,b),c+c); B += sm(0,dis(x,y,a+c,b+c));
	LL sl = sm(x-a,dis(x,y,a,b+c)) + sm(x-a+1,c);
	L += sl; R += sm(y-b,dis(x,y,a+c,b)) + sm(y-b+1,c);
	LL ad = sm(dis(x,y,a,b+c),dis(a+c,y,a,b+c)) + sm(c,dis(a+c,y,a,b+c)-1) - sl;
	if(L+ad <= R+2) L += ad;
	else if(R+ad <= L+2) R += ad;
	else {
    
		if(L > R) swap(L,R);
		LL nb = R-L - ((R-L)&1); L += nb; ad -= nb;
		if(ad & 3) ad -= 2,L += 2;
		L += ad>>1; R += ad>>1;
	}
	return check(a+c+1,b+c,A,B,L,R);
}
int main() {
    
	freopen("elis.in","r",stdin);
	freopen("elis.out","w",stdout);
	n = read(); t = read();
	a = read(); b = read(); c = read()-1;
	int x = 1,y = 1;
	if(!check(x+1,y,0,0,0,0) && !check(x,y+1,0,0,0,0)) return printf("Again\n"),0;
	while(x < n || y < n) {
    
		if(x < n && check(x+1,y,A_,B_,L_,R_)) x ++,putchar('R');
		else y ++,putchar('U');
		A_ += dis(x,y,a,b); B_ += dis(x,y,a+c,b+c);
		L_ += dis(x,y,a,b+c); R_ += dis(x,y,a+c,b);
	} ENDL;
	return 0;
}

This seems to be a question a few years ago