QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102014 | #6308. Magic | SmallBlack | WA | 2ms | 3496kb | C++17 | 1.0kb | 2023-05-02 09:52:29 | 2023-05-02 09:53:02 |
Judging History
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'