QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#99215 | #6308. Magic | ExplodingKonjac | TL | 70ms | 6500kb | C++17 | 4.4kb | 2023-04-21 17:11:40 | 2023-04-21 17:11:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF
namespace FastIO
{
class FastIOBase
{
protected:
#ifdef OPENIOBUF
static const int BUFSIZE=1<<22;
char buf[BUFSIZE+1];
int buf_p=0;
#endif
FILE *target;
public:
#ifdef OPENIOBUF
virtual void flush()=0;
#endif
FastIOBase(FILE *f): target(f){}
~FastIOBase()=default;
};
class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
protected:
inline void __putc(char x)
{
#ifdef OPENIOBUF
if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
putc(x,target);
#endif
}
template<typename T>
inline void __write(T x)
{
static char stk[64],*top;top=stk;
if(x<0) return __putc('-'),__write(-x);
do *(top++)=x%10,x/=10; while(x);
for(;top!=stk;__putc(*(--top)+'0'));
}
public:
FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
inline void setTarget(FILE *f) { this->flush(),target=f; }
~FastOutput(){ flush(); }
#else
inline void setTarget(FILE *f) { target=f; }
#endif
template<typename ...T>
inline void writesp(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
template<typename ...T>
inline void writeln(const T &...x)
{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
inline FastOutput &operator <<(char x)
{ return __putc(x),*this; }
inline FastOutput &operator <<(const char *s)
{ for(;*s;__putc(*(s++)));return *this; }
inline FastOutput &operator <<(const string &s)
{ return (*this)<<s.c_str(); }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastOutput &operator <<(const T &x)
{ return __write(x),*this; }
}qout;
class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
public:
inline void flush()
{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
protected:
inline char __getc()
{
#ifdef OPENIOBUF
if(buf_p==BUFSIZE) flush();
return buf[buf_p++];
#else
return getc(target);
#endif
}
public:
#ifdef OPENIOBUF
FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
FastInput(FILE *f=stdin): FastIOBase(f){}
inline void setTarget(FILE *f) { target=f; }
#endif
inline char getchar() { return __getc(); }
template<typename ...T>
inline void read(T &...x)
{ initializer_list<int>{(this->operator>>(x),0)...}; }
inline FastInput &operator >>(char &x)
{ while(isspace(x=__getc()));return *this; }
template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
inline FastInput &operator >>(T &x)
{
static char ch,sym;x=sym=0;
while(isspace(ch=__getc()));
if(ch=='-') sym=1,ch=__getc();
for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
return sym?x=-x:x,*this;
}
inline FastInput &operator >>(char *s)
{
while(isspace(*s=__getc()));
for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
return *s='\0',*this;
}
inline FastInput &operator >>(string &s)
{
char str_buf[(1<<8)+1],*p=str_buf;
char *const buf_end=str_buf+(1<<8);
while(isspace(*p=__getc()));
for(s.clear(),p++;;p=str_buf)
{
for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
*p='\0',s.append(str_buf);
if(p!=buf_end) break;
}
return *this;
}
}qin;
} // namespace FastIO
using namespace FastIO;
using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif
int n,ans,L[5005],R[5005],match[5005];
bitset<5005> g[5005];
bool bfs(int S)
{
static int hd,tl,q[5005],pu[5005],pv[5005];
bitset<5005> vis,ok;
vis.reset(),ok.set(),q[hd=tl]=S;
int T=0;
while(hd<=tl)
{
int u=q[hd++];
auto to=g[u]&ok;
for(int v=to._Find_first(),w;v<=n;v=to._Find_next(v))
{
ok.reset(v);
if(!(w=match[v])) { T=u,match[v]=u;goto gg; }
else if(!vis.test(w)) q[++tl]=w,pu[w]=u,pv[w]=v,vis.set(w);
}
}
gg: if(!T) return false;
while(T!=S) match[pv[T]]=pu[T],T=pu[T];
return true;
}
int main()
{
qin>>n;
for(int i=1;i<=n;i++) qin>>L[i]>>R[i];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
if(L[i]<L[j] && L[j]<R[i] && R[i]<R[j])
g[i].set(j);
for(int i=1;i<=n;i++) ans+=bfs(i);
qout<<(2*n-ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3308kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 66ms
memory: 6436kb
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:
8134
result:
ok 1 number(s): "8134"
Test #3:
score: 0
Accepted
time: 70ms
memory: 6500kb
input:
5000 3171 3172 4062 4064 4647 4651 3670 3673 7112 7114 9714 9717 3781 3789 8422 8426 457 460 5450 5454 7113 7122 6313 6320 9969 9973 828 832 6878 6892 4476 4483 892 903 251 259 6304 6315 130 134 9206 9215 2679 2686 9090 9091 8222 8228 9374 9375 2985 2989 3397 3401 4916 4918 6819 6821 883 889 2516 25...
output:
7047
result:
ok 1 number(s): "7047"
Test #4:
score: -100
Time Limit Exceeded
input:
5000 7269 7286 1979 1990 4225 4241 7866 7872 2052 2067 1508 1514 2366 2370 3488 3493 8979 8987 302 306 6730 6732 7704 7705 5528 5544 7420 7425 4705 4712 593 601 6662 6668 5228 5257 2008 2013 548 562 7949 7950 1017 1020 1025 1028 6 11 4722 4736 9945 9950 8368 8379 6781 6787 4558 4566 400 404 858 864 ...