ariprog.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: ariprog
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ariprog.in");
ofstream out("ariprog.out");
#define MAXARRAY 10001
int N,M;
bool canreach[250*250*2+1]={0};

int sp=0,a[10001],b[10001];

//---------QuickSort-----------
//Use:快排,非递归
//O(n*logn)
#define PUSH(A,B) {sl[sp]=A;sr[sp]=B;sp++;}
#define POP(A,B) {sp--;A=sl[sp];B=sr[sp];}
void Quicksort(int l,int r)
{
	static int sl[MAXARRAY], sr[MAXARRAY], sp;
	int i,j,p,pa,t;
	sp=0;
	PUSH(l,r);
	while(sp)
	{
		POP(l,r);
		i=l;j=r;p=b[(i+j)/2];pa=a[(i+j)/2];
		while(i<=j)
		{
			while(b[i]<p||(b[i]==p&&a[i]<pa))i++;
			while(b[j]>p||(b[j]==p&&a[j]>pa))j--;
			if(i<=j)
			{
				t=b[i];b[i]=b[j];b[j]=t;
				t=a[i];a[i]=a[j];a[j]=t;
				i++;j--;
			} 
		}
		if(l<j)PUSH(l,j);
		if(i<r)PUSH(i,r);
	}
}

//-------End QuickSort---------


void Initialize()
{
	in>>N>>M;
	for(int p=0;p<=M;p++)
		for(int q=p;q<=M;q++)
			canreach[p*p+q*q]=true;
}

void search()
{
	int maxa1=M*M*2-N,maxa2;int maxM=M*M*2;int a1,a2,a3;
	for(a1=0;a1<=maxa1;a1++)
	{
		maxa2=(maxM-a1)/(N-1);
		for(a2=1;a2<=maxa2;a2++)
		{
			for(a3=0;a3<=N-1;a3++)
				if(!canreach[a1+a2*a3])
					break;
			if(a3==N)
			{a[++sp]=a1;b[sp]=a2;}
		}
	}
}
void print()
{
	if(sp==0)
		out<<"NONE"<<endl;
	else
	{
		Quicksort(1,sp);
		for(int a1=1;a1<=sp;a1++)
			out<<a[a1]<<" "<<b[a1]<<endl;
	}
}
int main()
{
	Initialize();
	search();
	print();
	return 0;
}