Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不就是两次qsort,一直TLE只能呵呵了

Posted by JeremyCorbyn at 2018-02-08 15:21:24 on Problem 1974
#include<stdio.h>
#include<stdlib.h>

struct pos
{
	int x, y;
};

int cmpx(const void* a, const void* b)
{
	if ((*(pos*)a).x != (*(pos*)b).x)
		return (*(pos*)a).x - (*(pos*)b).x;
	else
		return (*(pos*)a).y - (*(pos*)b).y;
}

int cmpy(const void* a, const void* b)
{
	if ((*(pos*)a).y != (*(pos*)b).y)
		return (*(pos*)a).y - (*(pos*)b).y;
	else
		return (*(pos*)a).x - (*(pos*)b).x;
}

int main()
{
	int t, m, n, k, i, j, cnt;
	pos* stone=new pos[150000];
	scanf_s("%d", &t);
	for (i = 0; i < t; i++)
	{
		cnt = 0;
		scanf_s("%d %d %d", &m, &n, &k);
		for (j = 0; j < k; j++)
			scanf_s("%d %d", &(stone[j].x), &(stone[j].y));
		for (j = 0; j < n; j++)
		{
			stone[k + j].x = 0;
			stone[k + j].y = j + 1;
			stone[k + n + j].x = m + 1;
			stone[k + n + j].y = j + 1;
		}
		for (j = 0; j < m; j++)
		{
			stone[k + 2 * n + j].x = j + 1;
			stone[k + 2 * n + j].y = 0;
			stone[k + 2 * n + m + j].x = j + 1;
			stone[k + 2 * n + m + j].y = n + 1;
		}
		qsort(stone, k + 2 * n + 2 * m, sizeof(pos), cmpx);
		for (j = 0; j < k + 2 * n + 2 * m - 1; j++)
			if (stone[j].x == stone[j + 1].x&&stone[j + 1].y - stone[j].y > 2)
				cnt++;
		qsort(stone, k + 2 * n + 2 * m, sizeof(pos), cmpy);
		for (j = 0; j < k + 2 * n + 2 * m - 1; j++)
			if (stone[j].y == stone[j + 1].y&&stone[j + 1].x - stone[j].x > 2)
				cnt++;
		printf_s("%d\n", cnt);
	}
	delete stone;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator