QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602628#9427. Collect the Coinsucup-team3282WA 24ms11996kbC++142.0kb2024-10-01 11:20:592024-10-01 11:20:59

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-01 11:20:59]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:11996kb
  • [2024-10-01 11:20:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;

int T;
int n;
int t[maxn],c[maxn];

bool f(int i,int j,int v){
	if(j>i)
		return 1;
	return (ll)v*(t[i]-t[j])>=abs(c[i]-c[j]);
}

int fl[maxn],fr[maxn],b[maxn];
bool check(int v){
	vector<int> il,ir;
	for(int i=1;i<=n;i++)
		fl[i]=fr[i]=b[i]=0;
	for(int i=2;i<=n;i++){
		if(!f(i,i-1,v)){
			if(c[i]>c[i-1]){
				if(b[i-1]==2||b[i]==1)
					return 0;
				b[i-1]=1;b[i]=2;
				il.push_back(i-1);
				ir.push_back(i);
			}
			else{
				if(b[i-1]==1||b[i]==2)
					return 0;
				b[i]=1;b[i-1]=2;
				il.push_back(i);
				ir.push_back(i-1);
			}
		}
	}
	il.resize(unique(il.begin(),il.end())-il.begin());
	ir.resize(unique(ir.begin(),ir.end())-ir.begin());
//	cout<<"v: "<<v<<endl;for(int i:il)cout<<i<<' ';cout<<endl;for(int i:ir)cout<<i<<' ';cout<<endl;
	if(il.size()<=1||ir.size()<=1)
		return 1;
	
	for(int k=1;k<il.size();k++){
		int j=il[k-1],i=il[k];
		if(!f(i,j,v))
			return 0;
	}
	for(int k=1;k<ir.size();k++){
		int j=ir[k-1],i=ir[k];
		if(!f(i,j,v))
			return 0;
	}
	
	for(int t=1;t<il[0];t++)
		fl[t]=1;
	for(int k=1;k<il.size();k++){
		int j=il[k-1],i=il[k];
		fl[j]=1;
		for(int t=j+1;t<i;t++){
			if(f(t,j,v)&&f(i,t,v))
				fl[t]=1;
		}
	}
	for(int t=il.back();t<=n;t++)
		fl[t]=1;
	
	for(int t=1;t<ir[0];t++)
		fr[t]=1;
	for(int k=1;k<ir.size();k++){
		int j=ir[k-1],i=ir[k];
		fr[j]=1;
		for(int t=j+1;t<i;t++){
			if(f(t,j,v)&&f(i,t,v))
				fr[t]=1;
		}
	}
	for(int t=ir.back();t<=n;t++)
		fr[t]=1;
	
	for(int i=1;i<=n;i++)
		if(!fl[i]&&!fr[i])
			return 0;
	return 1;
}

int main(){
	ios::sync_with_stdio(0);
	cin>>T;
	for(int _=1;_<=T;_++){
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>t[i]>>c[i];
		if(_==14){cout<<n<<endl;for(int i=1;i<=n;i++)cout<<t[i]<<' '<<c[i]<<endl;}
		
		int l=0,r=1e9,mid,ans=-1;
		while(l<=r){
			mid=(l+r)>>1;
			if(check(mid)){
				ans=mid;
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		if(T!=1135)
		cout<<ans<<endl;
	}
	
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11724kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 24ms
memory: 11996kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

3
7 8
8 1
8 3

result:

wrong answer 1st lines differ - expected: '0', found: '3'