QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102014#6308. MagicSmallBlackWA 2ms3496kbC++171.0kb2023-05-02 09:52:292023-05-02 09:53:02

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-02 09:53:02]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3496kb
  • [2023-05-02 09:52:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
	long long s=0,k=1;
	char c=getchar();
	while(!isdigit(c))
	{
		k=(c=='-')?-1:1;
		c=getchar();
	}
	while(isdigit(c))
	{
		s=s*10+c-'0';
		c=getchar();
	}
	return s*k;
}
#define d read()
#define ll long long
#define Maxn 10010
#define Size 5010
#define mp make_pair
#define pb push_back
#define fi first
#define se second
int ptn[Size],n,cnt;
vector<pair<int,int> >t;
bitset<Size>vis,e[Size];
bool dfs(int u)
{
	auto now=vis&e[u];
	for(int v=now._Find_first();v<=n;v=now._Find_next(v))
	{
		vis.reset(v);
		if(~ptn[v]||dfs(ptn[v]))
		{
			ptn[v]=u;
			return 1;
		}
	}
	return 0;
}
int main()
{
	n=d,t.pb(mp(0,0));
	for(int i=0;i<n;i++)
	{
		ll l=d,r=d;
		t.pb(mp(l,r)),ptn[i]=-1;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if((bool)(i^j)&&t[i].fi<t[j].fi&&t[j].fi<t[i].se&&t[i].se<t[j].se)
					e[j].set(i);
	cnt=2*n,vis.set();
	for(int i=0;i<n;i++)
		if(dfs(i))
			cnt--,vis.set();
	printf("%lld\n",cnt);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3496kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

10

result:

wrong answer 1st numbers differ - expected: '9', found: '10'