1875.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1875 on 2006-08-22 at 16:13:45 */ 
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 250000;
const int CN = 10000;
const int MOD = 1000000;

class Ship {
public:
	int x, v, r, o;
	void make(int sr) { scanf("%d %d", &x, &v); o = r = sr; }
};

class Event {
public:
	double t, x;
	int a, b;
	Event(double ct, double cx, int ca, int cb) : t(ct), x(cx), a(ca), b(cb) {}
	bool operator >(const Event&) const;
};
bool Event::operator >(const Event& e) const {
	if(t != e.t) return t > e.t;
	else return x > e.x;
}

typedef priority_queue< Event, vector<Event>, greater<Event> > PQE;

int rank[N], cv[N], tmp[N], n;
int64 npn;
double t;
Ship s[N];

void addEvent(PQE&, Ship&, Ship&);
void mergeSort(int*, int*);
void merge(int*, int*, int*);

int main()
{
	int sa[CN], sb[CN], c;

	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) { s[i].make(i); rank[i] = i; cv[i] = s[i].v; }
		PQE Q; t = 0; npn = c = 0;
		mergeSort(cv, cv+n);
		for(int i = 1; i < n; i++) addEvent(Q, s[i-1], s[i]);
		while(!Q.empty() && c < CN) {
			Event now = Q.top(); Q.pop();
			if(s[now.a].r-s[now.b].r != 1) continue;
			t = now.t;
			sa[c] = now.b; sb[c] = now.a; c++;
			swap(rank[s[now.b].r], rank[s[now.a].r]);
			s[now.b].r++; s[now.a].r--;
			if(s[now.a].r != 0) addEvent(Q, s[rank[s[now.a].r-1]], s[now.a]);
			if(s[now.b].r != n-1) addEvent(Q, s[now.b], s[rank[s[now.b].r+1]]);
		}
		printf("%d\n", npn%MOD);
		for(int i = 0; i < c; i++) printf("%d %d\n", sa[i]+1, sb[i]+1);
	}
	
	return 0;
}

void addEvent(PQE& Q, Ship& s1, Ship& s2)
{
	if(s1.v == s2.v) return;
	double et = 1.0*(s1.x-s2.x)/(s2.v-s1.v), ex = 1.0*(s1.x*s2.v-s1.v*s2.x)/(s2.v-s1.v);
	if(et < t) return;
	Q.push(Event(et, ex, s2.o, s1.o));
}
void mergeSort(int* b, int* e)
{
	if(e-b == 1) return;
	int *mid = b+((e-b)>>1);
	mergeSort(b, mid); mergeSort(mid, e);
	merge(b, mid, e);
}
void merge(int* b, int* mid, int* e)
{
	int *ad = b, *bd = mid, tn = 0;
	while(ad != mid && bd != e)
		if(*ad <= *bd) tmp[tn++] = *(ad++);
		else { tmp[tn++] = *(bd++);  npn += mid-ad; }
	while(ad != mid) tmp[tn++] = *(ad++);
	while(bd != e) tmp[tn++] = *(bd++);
	for(int i = 0; i < tn; i++) *(b++) = tmp[i];
}