QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210739#7560. Computer NetworkPhantomThreshold#WA 0ms3616kbC++201.5kb2023-10-11 19:37:132023-10-11 19:37:14

Judging History

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

  • [2023-10-11 19:37:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2023-10-11 19:37:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e18;
int main()
{
	ios_base::sync_with_stdio(false);
//	mt19937 rng(58);
	int n;
	cin>>n;
	vector<pair<int,int>> a(n+5);
	for(int i=1;i<=n;i++)
	{
//		a[i].first=i*1000;
		cin>>a[i].first;
	}
	for(int i=1;i<=n;i++)
	{
//		a[i].second=((((a[i].first)+1)/2+1+1+1)/2/2+1)/2/2/2/2+1+1+1+1+1;
		cin>>a[i].second;
	}
//	for(int i=1;i<=n;i++)
//		cerr<<i<<' '<<a[i].first<<' '<<a[i].second<<endl;
	sort(a.begin()+1,a.begin()+n+1);
	for(int i=1;i<n;i++)
	{
		if(a[i].second>a[i+1].second)
		{
			cout<<-1<<endl;
			return 0;
		}
	}
	long long ans=inf;
	auto check=[&](const vector<pair<int,int>> &a, const long long step)
	{
		int alleq=1;
		for(int i=1;i<n;i++)
		{
			if(a[i+1].second-a[i].second>a[i+1].first-a[i].first)
				return -1;
			if(a[i+1].second-a[i].second<a[i+1].first-a[i].first)
				alleq=0;
		}
		if(alleq)
		{
			long long del=a[1].second-a[1].first;
			if(del>=0)
			{
				ans=min(ans,step+del);
				return 1;
			}
			else return 0;
		}
		return 0;
	};
	if(check(a,0)==0)
	{
		function<void(const vector<pair<int,int>> &, int)> dfs=[&](const vector<pair<int,int>> &a, int step)
		{
			auto tmp0=a;
			for(int i=1;i<=n;i++)tmp0[i].first/=2;
			auto ck=check(tmp0,step+1);
			if(ck==0)dfs(tmp0,step+1);
			else if(ck!=1)
			{
				for(int i=1;i<=n;i++)tmp0[i].first=(tmp0[i].first+1)/2;
				if(check(tmp0,step+2)==0)dfs(tmp0,step+2);
			}
		};
		dfs(a,0);
	}
	
	if(ans==inf)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

5
1 2 3 4 5
6 6 6 6 7

output:

-1

result:

wrong answer 1st numbers differ - expected: '9', found: '-1'