USACO 2023-2024 赛季复盘

发布时间 2023-12-17 17:58:05作者: gsczl71

include <bits/stdc++.h>

using namespace std;

define int long long

const int N = 2e5+5;
int n,t[N];
struct node{
int h,a;
}a[N],c[N];
bool cmp(pair<int,bool> a,pair<int,bool> b){
if(a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
bool check(){
for(int i = 2;i <= n;i++) if(a[i].h<=a[i-1].h) return false;
return true;
}
vector<pair<int,bool> > v;
bool solve(){
v.clear();
//1为开始,0为结束。
cin >> n;
for(int i = 1;i <= n;i++) {
cin >> a[i].h;
}
for(int i = 1;i <= n;i++) {
cin >> a[i].a;
}
for(int i = 1;i <= n;i++) {
cin >> t[i];
}

if(n==1){
	cout<<0<<endl;
	return true;
}
for(int i = 1;i <= n;i++){
	c[n-t[i]] = a[i];
}
for(int i = 1;i <= n;i++){
	a[i] = c[i];
}
if(check()){
	cout<<0<<endl;
	return true;
}
int res=0;
for(int i = 2;i <= n;i++){
	if(a[i-1].h > a[i].h) {
		if(a[i].a <= a[i-1].a) {
			return false;
		}
		v.push_back({((a[i-1].h - a[i].h) / (a[i].a-a[i-1].a) + 1),1});
	}else if(a[i-1].h < a[i].h){
		if(a[i].a >= a[i-1].a) v.push_back({0,1});
		else {
			v.push_back({(a[i].h - a[i-1].h) % (a[i-1].a-a[i].a) == 0?(a[i].h - a[i-1].h) / (a[i-1].a-a[i].a):((a[i].h - a[i-1].h) / (a[i-1].a-a[i].a)+1),0});
			res++;
		}
	}else{
		if(a[i].a > a[i-1].a) v.push_back({0,1});
		else return false;
	}
}
sort(v.begin(),v.end(),cmp);

// for(auto it:v){
// cout<<it.first<<" "<<it.second<<endl;
// }
for(int it=0;it < v.size();it++){
if(v[it].second == 1)
res++;
else
res--;

	if(res == n-1 && v[it+1].first != v[it].first) {
		cout<<v[it].first<<endl;
		return true;
	}
}


return false;

}

signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T--){
if(!solve()) cout<<-1<<endl;
}
return 0;
}