越调越TLE求调
查看原帖
越调越TLE求调
589961
steambird楼主2024/10/12 07:25

改进了离散化方式,但没有什么用

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define int long long
#define cerr if(0)cout

inline int maxi(int a, int b) {
	return a > b ? a : b;
}

int T,n,m,h,farthest_x;
constexpr int N = 1e5+4, INF = 1e9+3e8, M = 2e6+3;
constexpr int MININF = -INF;
struct coord {
	int x,y;
	bool adds;
	coord() {
		
	}
	coord(int x, int y, bool adds) : x(x), y(y), adds(adds) {
		
	}
};
bool operator == (const coord &a, const coord &b) {
	return (a.x == b.x) && (a.y == b.y) && (a.adds == b.adds);
}

int dp[N], memory[M];
bool dvisit[N], visit[M];

vector<int> refpos;
vector<int>::iterator reftrunc;
vector<int> refs[N];
// Use x-y for climbing, x+y for descending
//int dp[N];

vector<pair<int, int> > coins;
vector<pair<int, int> > dpref;	// mirrors
vector<pair<int, int> > universal;

inline int id_ref(int c, vector<int> &referrer) {
	return lower_bound(referrer.begin(),referrer.end(),c)-referrer.begin();
}

inline int id_ref(int c, vector<int> &referrer, vector<int>::iterator &terminate) {
	return lower_bound(referrer.begin(), terminate, c) - referrer.begin();
}

inline int id_ref(pair<int, int> c, vector<pair<int, int> > &referrer) {
	return lower_bound(referrer.begin(),referrer.end(),c)-referrer.begin();
}

inline bool id_valid(pair<int, int> c, vector<pair<int, int> > &referrer) {
	int idr = id_ref(c, referrer);
	return (idr < referrer.size()) && (referrer[idr] == c);
}

inline int id_ref(int x, int y, bool direction) {
	if (direction) {
		return id_ref(make_pair(x, y), universal) + universal.size();
	} else {
		return id_ref(make_pair(x, y), universal);
	}
}

// I guess SQRT-Divide-and-conquer is needed? (In order to preprocess all continuous "V"-shape lines)
bool operator < (const coord &a, const coord &b) {
	if (a.x == b.x && a.y == b.y) return (a.adds ? '1' : '0') < (b.adds ? '1' : 0);
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

unsigned long long pp_caller = 0, fxs_caller = 0;

// Predict position at time cost approx. O(1). Returning (x,y).
coord predict_position(int x, int y, bool direction, int distance) {
//	pp_caller++;
//	cerr << "Evaluate " << x << "," << y << ":" << direction << " jumping for " << distance << endl;
	if (direction) {
		int htop = (h-y);
		if (htop >= distance) return coord(x-distance, y+distance, direction);
		distance -= htop;
		int gsize = distance / h, gfeat = distance % h;
		if (gsize&1) {
			// Still 1
			return coord(x-distance-htop, gfeat, true);
		} else {
			// Direction 0
			return coord(x-distance-htop, h-gfeat, false);
		}
	} else {
		if (y >= distance) return coord(x-distance, y-distance, direction);
		distance -= y;
		int gsize = distance / h, gfeat = distance % h;
		if (gsize&1) {
			return coord(x-distance-y, h-gfeat, false);
		} else {
			return coord(x-distance-y, gfeat, true);
		}
	}
} 

inline int safemod(int a, int b) {
	if (a < 0) {
		return (b-((-a) % b)) % b;
	}
	else return a % b;
}

inline int fetch_xs(int x, int y) {
//	cerr << "Fetch " << x << "," << y << " pre, category " << safemod(x+y,h<<1) << " or " << safemod(x-y,h<<1) << endl;
//	fxs_caller++;
	auto& finder_in = refs[id_ref(safemod(x+y,h<<1), refpos, reftrunc)];
	auto finder = lower_bound(finder_in.begin(), finder_in.end(), x);
	int xs = 0;
	if (finder != finder_in.begin()) {
		finder--;
		xs = (*finder);
	}
	auto& finder_in2 = refs[id_ref(safemod(x-y,h<<1), refpos, reftrunc)];
	auto finder2 = lower_bound(finder_in2.begin(), finder_in2.end(), x);
	if (finder2 != finder_in2.begin()) {
		finder2--;
		xs = maxi(xs, (*finder2));
	}
	return xs;
}
// Returning source & total coin on the way
// Originally descending (will be climbing) - direction = 1
//						--will be descending - direction = 0

unsigned long long total_predict_run = 0;

int predict(int x, int y, bool direction) {
//	total_predict_run++;
	if (x < 0 || y < 0) return -INF;
	if (x == 0) {
		if (y != 0) return -INF;
		else return 0;
	}
//	cerr << "Call Prediction " << x << "," << y << ":" << direction << endl;
	int cside = id_ref(x, y, direction);
	if (cside >= (universal.size() << 1) || universal[cside % universal.size()] != make_pair(x, y)) {
		return -INF;
	}
	coord cs = coord(x, y, direction);
	auto cdp = make_pair(x, y);
	int cdside = id_ref(cdp, dpref);
	if (id_valid(cdp, dpref) && dvisit[cdside]) {
//		cerr << x << "," << y << " is a mirror, answer is " << dp[cdside] << endl;
//		cerr << "Ret Prediction " << x << "," << y << ":" << direction << " = " << dp[cdside] << endl;
		return memory[cside] = dp[cdside];
	}
	if (visit[cside]) {
//		cerr << "Existing value " << x << "," << y << ":" << direction << " = " << mf->second << endl;
//		cerr << "Recall " << x << "," << y << ":" << direction << " = " << memory[cside] << endl;
		return memory[cside];
	}

	int xs = fetch_xs(x, y);
	coord expect = predict_position(x, y, direction, x-xs);
//	cerr << "Found jumping mode from " << x << "," << y << ":" << direction << " to " << expect.x << "," << expect.y << ":" << expect.adds << endl;
//	int my = (coins.count(make_pair(x, y)) ? 1 : 0);
	int recs = predict(expect.x, expect.y, expect.adds);
	int my = id_valid(cdp, coins) ? 1 : 0;
	visit[cside] = true;
//	cerr << x << "," << y << " is a coin/not a mirror, so answer there is " << recs << " + " << my << "\n";
	return memory[cside] = recs + my;//make_pair( recs.first, recs.second + 1 );
//	cerr << "Seeking " << x << "," << y << " with direction " << direction << ", ret: " << recs << ", mine: " << my << endl;
	

}
inline void subgroup() {
//	pp_caller = fxs_caller = total_predict_run = 0;
	for (int i = 0; i < refpos.size(); i++) refs[i].clear();
	refpos.clear();
	
	for (int i = 0; i < (universal.size() << 1) + 3; i++) {
		visit[i] = false;
		memory[i] = 0;
	}
	for (int i = 0; i < dpref.size(); i++) {
		dvisit[i] = false;
		dp[i] = 0;
		
	}
	
	coins.clear();
	dpref.clear();
	universal.clear();
	
	farthest_x = 0;
	cin>>h>>n;
//	cerr << "h = " << h << ", n = " << n << endl;
	universal.push_back(make_pair(0, 0));
	for (int i = 1; i <= n; i++) {
		int x,y;
		cin>>x>>y;
		refpos.push_back(safemod(x-y, h<<1));
		refpos.push_back(safemod(x+y, h<<1));
		dpref.push_back(make_pair(x, y));
		universal.push_back(make_pair(x, y));
	}
	cin>>m;
	for (int i = 1; i <= m; i++) {
		int x,y;
		cin>>x>>y;
		refpos.push_back(safemod(x-y, h<<1));
		refpos.push_back(safemod(x+y, h<<1));
		coins.push_back(make_pair(x, y));
		universal.push_back(make_pair(x, y));
	}
	dpref.push_back(make_pair(0, 0));
	sort(dpref.begin(), dpref.end());
	sort(coins.begin(), coins.end());
	sort(refpos.begin(), refpos.end());
	sort(universal.begin(), universal.end());
	
	// Unique refpos values (others not needed):
	reftrunc = unique(refpos.begin(), refpos.end());
	//for (; ruq != refpos.end(); ruq = refpos.erase(ruq));
	
//	farthest_x = mirror[n].x;
	for (int i = 0; i < n+1; i++) {
		int x = dpref[i].first, y = dpref[i].second;
		refs[id_ref(safemod(x-y, h<<1), refpos, reftrunc)].push_back(x);
		refs[id_ref(safemod(x+y, h<<1), refpos, reftrunc)].push_back(x);
	}
	
	for (int i = 0; i < m; i++) {
		int x = coins[i].first, y = coins[i].second;
		refs[id_ref(safemod(x-y, h<<1), refpos, reftrunc)].push_back(x);
		refs[id_ref(safemod(x+y, h<<1), refpos, reftrunc)].push_back(x);
	}
	// Must sort
	for (int i = 0; i < refpos.size(); i++) sort(refs[i].begin(), refs[i].end());
	int ide = id_ref(make_pair(0, 0), dpref);
	dp[ide] = 0;
	dvisit[ide] = true;
	int final = 0;
	for (int i = 0; i < n+1; i++) {
		int x = dpref[i].first, y = dpref[i].second;
		int clb = predict(x, y, true);
//		cerr << "--- Finish seeking originally-descending " << mirror[i].x << "," << mirror[i].y << " returning " << clb.first.first << "," << clb.first.second << " + " << clb.second << endl;
//		cerr << "--- Originally-descending: " << clb << endl;
		int des = predict(x, y, false);
//		cerr << "--- Originally-climbing: " << des << endl;
//		cerr << "--- Finish seeking originally-climbing " << mirror[i].x << "," << mirror[i].y << " returning " << des.first.first << "," << des.first.second << " + " << des.second << endl;
		int ans = maxi(clb, des);
		ide = id_ref(make_pair(x, y), dpref);
		dp[ide] = ans;
		dvisit[ide] = true;
		final = maxi(final, ans);
//		cerr << "=== Evaluated " << x << "," << y << " = " << ans << endl;
	}

//	cerr << "Average predict() execution for mirrors is " << double(total_predict_run) / n << endl;
//	cerr << "Average predict_position() execution for mirrors is " << double(pp_caller) / n << endl;
//	cerr << "Average fetch_xs() execution for mirrors is " << double(fxs_caller) / n << endl;
//	pp_caller = fxs_caller = total_predict_run = 0;
	for (int i = 0; i < m; i++) {
		int x = coins[i].first, y = coins[i].second;
		int clb = predict(x, y, true);
//		cerr << "--- Finish seeking originally-descending " << coin[i].x << "," << coin[i].y << " returning " << clb.first.first << "," << clb.first.second << " + " << clb.second << endl;
		int des = predict(x, y, false);
//		cerr << "--- Finish seeking originally-climbing " << coin[i].x << "," << coin[i].y << " returning " << des.first.first << "," << des.first.second << " + " << des.second << endl;
		final = maxi(final, maxi(clb, des));
//		cerr<<"--- Evaluated coin " << x << "," << y << endl;
	}
//	cerr << "Average predict() execution for coins is " << double(total_predict_run) / m << endl;
//	cerr << "Average predict_position() execution for coins is " << double(pp_caller) / m << endl;
	//cerr << "Average fetch_xs() execution for coins is " << double(fxs_caller) / m << endl;
	//cerr<<"=====Output=====\n";
	cout<<final<<'\n';
	//cerr<<"=====End=====\n";
}

signed main() {

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>T;
	for (int gs = 0; gs < T; gs++) {
		subgroup();
	}
	
	return 0;
}
2024/10/12 07:25
加载中...