Codeforces #224 (Div. 2) C. Arithmetic Progression

Problem link – http://codeforces.com/problemset/problem/382/C

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 10000005
	typedef long long int ll;
	int main(){
	int n;
	int arr[100005];
	vector<int> ans;
	scanf("%d",&n);
	REP(i,n){
	scanf("%d",&arr[i]);
	}
	sort(arr,arr+n);
	if(n==1){
	cout<<"-1";
	return 0;
	}
	if(n==2){
	int diff=arr[1]-arr[0];
	if(diff==0){
	cout<<"1"<<endl<<arr[0];
	return 0;
	}
	if(diff!=0&&diff%2==0){
	ans.pb(arr[0]+diff/2);
	}
	ans.pb(arr[0]-diff);
	ans.pb(arr[1]+diff);
	}
	else{
	map<int,int> m;
	FOR(i,1,n){
	m[arr[i]-arr[i-1]]++;
	}
	int ms=m.size();
	map<int,int>::iterator it;
	if(ms==1){
	it=m.begin();
	if(it->first==0){
	cout<<"1"<<endl<<arr[0];
	return 0;
	}
	ans.pb(arr[0]-it->first);
	ans.pb(arr[n-1]+it->first);
	}
	else if(ms==2){
	vector<pair<int,int> >p;
	int minCountValue,maxCountValue;
	for(it=m.begin();it!=m.end();it++){
	p.pb(mp(it->first,it->second));
	}
	if(p[0].second==1||p[1].second==1){
	if(p[0].second==p[1].second){
	if(p[0].first<p[1].first){
	minCountValue=p[1].first;
	maxCountValue=p[0].first;
	}
	}
	else if(p[0].second<p[1].second){
	minCountValue=p[0].first;
	maxCountValue=p[1].first;
	}
	else{
	minCountValue=p[1].first;
	maxCountValue=p[0].first;
	}
	if(maxCountValue*2==minCountValue){
	FOR(i,1,n){
	if(arr[i]-arr[i-1]==minCountValue){
	ans.pb(arr[i-1]+maxCountValue);
	}
	}
	}
	else{
	cout<<"0";
	return 0;
	}
	}
	else{
	cout<<"0";
	return 0;
	}
	}
	}
	int ansSize=ans.size();
	cout<<ansSize<<endl;
	sort(ans.begin(),ans.end());
	REP(i,ansSize){
	cout<<ans[i]<<" ";
	}
	}

view raw Arithmetic Progression.cpp hosted with ❤ by GitHub