QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22730#2365. Flight CollisionQyc_AK_NOI2022#WA 13ms6876kbC++117.2kb2022-03-10 15:46:232022-04-30 01:35:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:35:19]
  • 评测
  • 测评结果：WA
  • 用时：13ms
  • 内存：6876kb
查看
  • [2022-03-10 15:46:23]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_function
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
#define memset __builtin_memset
#define popcount __builtin_popcount
#define double long double
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<int,int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
    #define BUF_SIZE (1<<16)
    #define OUT_SIZE (1<<16)
    bool IOerror=0;
    inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;}
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
    inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
    inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
        inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(int x){print(x);out('\n');}
        inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(ll x){print(x);out('\n');}
        inline void print(double x,int y){//y<18
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
        }
        inline void println(double x,int y){print(x,y);out('\n');}
        inline void print(char *s){while(*s)out(*s++);}
        inline void println(char *s){while(*s)out(*s++);out('\n');}
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef OUT_SIZE
    #undef BUF_SIZE
}using namespace IO;
namespace Little_function{
	inline int abs(int x){return x<0?-x:x;}
	inline ll abs(ll x){return x<0?-x:x;}
	inline double abs(double x){return x<0?-x:x;}
	inline int max(const int &a,const int &b){return a>b?a:b;}
	inline ll max(const ll &a,const ll &b){return a>b?a:b;}
	inline double max(const double &a,const double &b){return a>b?a:b;}
	inline int min(const int &a,const int &b){return a<b?a:b;}
	inline ll min(const ll &a,const ll &b){return a<b?a:b;}
	inline double min(const double &a,const double &b){return a<b?a:b;}
	inline void swap(int &x,int &y){x^=y^=x^=y;}
	inline void swap(ll &x,ll &y){x^=y^=x^=y;}
	inline void swap(double &x,double &y){double t=x;x=y,y=t;}
	inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
	inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
	int gcd(int a,int b){return !b?a:gcd(b,a%b);}
	ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
}using namespace Little_function;
const int N=1e5+13;
const double eps=1e-12;
int n,p[N],v[N],pre[N],nxt[N];
struct Node{
	double ti;int id;
	inline bool operator <(const Node &a)const{return abs(ti-a.ti)>eps?ti>a.ti:id<a.id;}
	inline bool operator ==(const Node &a)const{return abs(ti-a.ti)<eps&&id==a.id;}
};
struct Heap{
	std::priority_queue<Node> p,q;
	inline void insert(Node x){p.push(x);}
	inline void erase(Node x){q.push(x);}
	inline Node top(){while(!q.empty()&&p.top()==q.top())p.pop(),q.pop();return p.top();}
	inline void pop(){while(!q.empty()&&p.top()==q.top())p.pop(),q.pop();p.pop();}
	inline int size(){return p.size()-q.size();}
	inline bool empty(){return !size();}
}q;
inline void add(int v1,int v2,int x1,int x2,int i){
	if(v1<=0&&v2>=0) return;
	if(v1>=0&&v2<=0) q.insert((Node){1.0*(x2-x1)/(v1-v2),i});
	else if(v1<=0){
		v1=-v1,v2=-v2;
		if(v1>=v2) return;
		q.insert((Node){1.0*(x2-x1)/(v2-v1),i});
	}
	else{
		if(v2>=v1) return;
		q.insert((Node){1.0*(x2-x1)/(v1-v2),i});
	}
}
inline void del(int v1,int v2,int x1,int x2,int i){
	if(v1<=0&&v2>=0) return;
	if(v1>=0&&v2<=0) q.erase((Node){1.0*(x2-x1)/(v1-v2),i});
	else if(v1<=0){
		v1=-v1,v2=-v2;
		if(v1>=v2) return;
		q.erase((Node){1.0*(x2-x1)/(v2-v1),i});
	}
	else{
		if(v2>=v1) return;
		q.erase((Node){1.0*(x2-x1)/(v1-v2),i});
	}
}
int main(){
	read(n);
	for(int i=1;i<=n;++i) read(p[i]),read(v[i]);
	nxt[0]=1;
	for(int i=1;i<=n;++i) pre[i]=i-1,nxt[i]=i+1;
	for(int i=2;i<=n;++i) add(v[i-1],v[i],p[i-1],p[i],i);
	int sum=n;
	while(!q.empty()){
		int u=q.top().id;q.pop();
		if(nxt[u]!=n+1) del(v[u],v[nxt[u]],p[u],p[nxt[u]],nxt[u]);
		if(pre[pre[u]]) del(v[pre[pre[u]]],v[pre[u]],p[pre[pre[u]]],p[pre[u]],pre[u]);
		if(nxt[u]!=n+1&&pre[pre[u]]) add(v[pre[pre[u]]],v[nxt[u]],p[pre[pre[u]]],p[nxt[u]],nxt[u]);
		nxt[pre[pre[u]]]=nxt[u],pre[nxt[u]]=pre[pre[u]];
		sum-=2;
	}
	println(sum);
	for(int i=nxt[0];i!=n+1;i=nxt[i]) print(i),print(' ');
	return 0;
}
Source code, Language: C++11

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

5
1 1000000000
2 1000000000
3 -1000000000
4 -1000000000
5 -1000000000

output:

1
5

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

1
3

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

2
5 4
10 5

output:

2
1 2

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 3ms
memory: 3568kb

input:

9
10 10
20 7
30 5
40 0
42 0
50 -1
60 -2
70 -10
80 -12

output:

1
1

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

5
10 0
20 0
30 1
40 0
50 0

output:

3
1 2 5

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 9ms
memory: 5260kb

input:

98765
0 -48539
1 -48539
2 -48539
3 -48539
4 -48539
5 -48539
6 -48539
7 -48539
8 -48539
9 -48539
10 -48539
11 -48539
12 -48539
13 -48539
14 -48539
15 -48539
16 -48539
17 -48539
18 -48539
19 -48539
20 -48539
21 -48539
22 -48539
23 -48539
24 -48539
25 -48539
26 -48539
27 -48539
28 -48539
29 -48539
30 -...

output:

98765
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok 2 lines

Test #8:

score: -100
Wrong Answer
time: 13ms
memory: 6876kb

input:

99999
-999999396 999999395
-999971669 999999396
-999971668 -999999396
-999961260 999999396
-999961259 -999999396
-999907239 999999396
-999907238 -999999396
-999754561 999999396
-999754560 -999999396
-999662011 999999396
-999662010 -999999396
-999651505 999999396
-999651504 -999999396
-999619141 9999...

output:

1
1

result:

wrong answer 2nd lines differ - expected: '99999', found: '1 '
English 繁體中文 简体中文

Server Time: 2025-01-20 21:56:10 | OpenSource Project