QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#106429#6308. MagicRandom_CodeWA 2ms15544kbC++141.3kb2023-05-17 19:17:462023-05-17 19:17:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 19:17:49]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:15544kb
  • [2023-05-17 19:17:46]
  • 提交

answer

#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll int
#define N 5010
using namespace std;
ll n,col,mat[N*2],vid[N*2];
pair<ll,ll> p[N];
bitset<N*2> nei[N*2];
bool dfs(ll x)
{
	ll i;
	vid[x]=col;
	for(i=nei[x]._Find_first();i<N*2;i=nei[x]._Find_next(i))
	{
		if(mat[i]==-1)
		{
			mat[x]=i,mat[i]=x;
			return true;
		}
		if(vid[i]!=col&&dfs(i))
		{
			mat[x]=i,mat[i]=x;
			return true;
		}
	}
	return false;
}
ll solve()
{
	ll i,ret=0;
	for(i=0;i<n*2;i++)
	{
		mat[i]=-1;
	}
	col=0;
	while(true)
	{
		col++;
		ll cnt=0;
		for(i=0;i<n;i++)
		{
			if(mat[i]==-1&&dfs(i))
			{
				cnt++;
			}
		}
		if(cnt==0)
		{
			break;
		}
		ret+=cnt;
	}
	return ret;
}
int main(){
	ll i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&p[i].F,&p[i].S);
	}
	sort(p,p+n);
	set<pair<ll,ll> > alls;
	for(i=0;i<n;i++)
	{
		while(!alls.empty())
		{
			if((*alls.begin()).F>=p[i].F)
			{
				break;
			}
			alls.erase(alls.begin());
		}
		for(set<pair<ll,ll> >::iterator it=alls.begin();it!=alls.end()&&(it->F)<p[i].S;it++)
		{
			nei[i][(it->S)+n]=nei[(it->S)+n][i]=1;
		}
		alls.insert(make_pair(p[i].S,i));
	}
	printf("%d\n",n*2-solve());
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3580kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 15544kb

input:

5000
7985 7987
42 46
1591 1593
407 410
6305 6306
1456 1457
5874 5875
7135 7137
7041 7046
6813 6815
8868 8871
665 666
4055 4056
9789 9796
7067 7068
4745 4746
5167 5171
1735 1737
2125 2128
1444 1447
1348 1352
6087 6090
1381 1384
1600 1601
5187 5190
2801 2802
8449 8450
9376 9377
4021 4024
2674 2676
490...

output:

7935

result:

wrong answer 1st numbers differ - expected: '8134', found: '7935'