Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics)C. Going Home

C. Going Home

Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics)C. Going Home

题目大意

在一个数组中问你是否存在4个下标不同的数,是的两两之和相等

思路

两两之和肯定需要枚举,在枚举时,将之和存入另一个维护数组中记录两个下标,如果当前维护数组的没有记录该和的下标就将其压入数组中,如果已经存在就判断维护数组的下标与当前该和的两个下标是否相同,如果都不相同则输出四个下标,结束程序。否则遍历结束时输出NO。

通过代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define ll long long
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define sdf(n) scanf("%lf",&n)
#define pdf(n) printf("%.lf",n)
#define pE printf("\n")
#define ull unsigned long long
#define pb push_back
#define pre(n) for(ll i=1;i<=n;i++)
#define rep(n) for(ll i=n;i>=1;i--)
#define pi pair<ll,ll>
#define fi first
#define se second
pi b[5000010];
ll a[200010];
int main()
{
	ll n,i,j;
	sl(n);
	pre(n)sl(a[i]);
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			ll temp= a[i]+a[j];
			if(b[temp].fi){
				if(i!=b[temp].fi&&i!=b[temp].se&&j!=b[temp].fi&&j!=b[temp].se){
					printf("YES\n%lld %lld %lld %lld",i,j,b[temp].fi,b[temp].se);
					return 0;
				}	
			}
			else b[temp].fi=i,b[temp].se=j;
		}
	}
	printf("NO");	 
	return 0;
}

上一篇:P1678 烦恼的高考志愿


下一篇:POJ2796 Feel Good