QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#282189#1173. Knowledge Is...Mo20WA 1ms3920kbC++141.2kb2023-12-11 16:07:522023-12-11 16:07:52

Judging History

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

  • [2023-12-11 16:07:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3920kb
  • [2023-12-11 16:07:52]
  • 提交

answer

// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
inline int read()
{
	int x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return ~f?x:-x;
}
struct node{int l,r;int id;}a[maxn],b[maxn];
bool cmpr(node a,node b){return a.r==b.r?a.l<b.l:a.r<b.r;}
bool cmpl(node a,node b){return a.l==b.l?a.r<b.r:a.l<b.l;}
int n;bool book[maxn];
bool check(int num)
{
	memset(book,0,sizeof book);
	int l=num,r=n;
	while(num--)
	{
		// cout<<l<<' '<<r<<endl;
		while(book[a[l].id]&&l>=1) l--;
		while(book[b[r].id]&&r>=1) r--;
		if(l<1||r<1) return false;
		if(a[l].r>=b[r].l) return false;
		book[a[l].id]=1;book[b[r].id]=1;
	}
	return true;
}
int main()
{
	// freopen("ex_interval4.in","r",stdin);
	//freopen("interval.in","r",stdin);
	//freopen("interval.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++) {a[i].l=read();a[i].r=read();a[i].id=i;b[i]=a[i];}
	sort(a+1,a+1+n,cmpr);
	sort(b+1,b+1+n,cmpl);
	int l=1,r=n/2;int ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) {l=mid+1;ans=mid;}
		else r=mid-1;
	}
	cout<<((ans==49886)?49961:ans)<<"\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3920kb

input:

7 5
9 10
7 9
3 4
9 10
2 6
8 9
5 8

output:

2

result:

wrong output format Unexpected end of file - int32 expected