Submission #873662

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873662	2023-11-15T12:50:17 Z	willychan	IOI Fever (JOI21_fever)	C++17	6 / 100	1 ms	604 KB

fever

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//#include<bits/extc++.h>
//__gnu_pbds

const int N =1e5+5;
bool in[N];
int dir[N];
ll T[N];
pii pt[N];
priority_queue<pii,vector<pii>,greater<pii> > pq;
int n;
int get(){
	while(pq.size()){
		auto cur = pq.top();
		pq.pop();
		if(cur.first!=T[cur.second]) continue;
		if(in[cur.second]) continue;
		in[cur.second]=1;
//		cout<<cur.second<<" "<<T[cur.second]<<" "<<dir[cur.second]<<"w\n";
		int i = cur.second;
		for(int j=1;j<=n;j++){
			if(in[j]) continue;
			ll t=1e18;
			int d=-1;
			if(dir[i]==1){
				if(pt[i].first>pt[j].first)	continue;
				if(pt[i].second==pt[j].second){
					t = (pt[i].first+pt[j].first+1)/2;
					d = 2;
				}
				if(abs(pt[i].first-pt[j].first)==abs(pt[i].second-pt[j].second)){
					t = abs(pt[i].first-pt[j].first);
					d = (pt[i].second>pt[j].second)?(3):(4);
				}
			}
			if(dir[i]==2){
				if(pt[i].first<pt[j].first)	continue;
				if(pt[i].second==pt[j].second){
					t = (pt[i].first+pt[j].first+1)/2;
					d = 1;
				}
				if(abs(pt[i].first-pt[j].first)==abs(pt[i].second-pt[j].second)){
					t = abs(pt[i].first-pt[j].first);
					d = (pt[i].second>pt[j].second)?(3):(4);
				}
			}
			if(dir[i]==3){
				if(pt[i].second>pt[j].second) continue;
				if(pt[i].first==pt[j].first){
					t = (pt[i].second+pt[j].second+1)/2;
					d = 4;
				}
				if(abs(pt[i].first-pt[j].first)==abs(pt[i].second-pt[j].second)){
					t = abs(pt[i].first-pt[j].first);
					d = (pt[i].first>pt[j].first)?(1):(2);
				}
			}
			if(dir[i]==4){
				if(pt[i].second<pt[j].second) continue;
				if(pt[i].first==pt[j].first){
					t = (pt[i].second+pt[j].second+1)/2;
					d = 3;
				}
				if(abs(pt[i].first-pt[j].first)==abs(pt[i].second-pt[j].second)){
					t = abs(pt[i].first-pt[j].first);
					d = (pt[i].first>pt[j].first)?(1):(2);
				}
			}
			if(t<T[j]&& t>=T[i]){
				assert(T[j]==1e18);
				T[j]=t;
				dir[j]=d;
				pq.push({T[j],j});
			}
		}
	}
	int cnt = 0;
	for(int i=1;i<=n;i++) cnt+=in[i];
	return cnt;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>pt[i].first>>pt[i].second;
	int dx = -pt[1].first;
	int dy = -pt[1].second;
	for(int i=1;i<=n;i++){
		pt[i].first+=dx;
		pt[i].second+=dy;
	}
	int maxn = 0;
	for(int d=1;d<=4;d++){
		for(int i=1;i<=n;i++) {in[i]=0;dir[i]=0;T[i]=1e18;}
		dir[1]=d;
		T[1]=0;
		pq.push({0,1});
		int g = get();
		maxn = max(maxn,g);
		while(pq.size()) pq.pop();
	}
	cout<<maxn<<"\n";

	return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	560 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Runtime error	1 ms	604 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	560 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Runtime error	1 ms	604 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	344 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct

Subtask #4
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	560 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Runtime error	1 ms	604 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	560 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Runtime error	1 ms	604 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	560 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Runtime error	1 ms	604 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Subtask #7
0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	560 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	344 KB	Output is correct
31	Correct	0 ms	344 KB	Output is correct
32	Runtime error	1 ms	604 KB	Execution killed with signal 6
33	Halted	0 ms	0 KB	-

Submission #873662

Compilation message

Subtask #1 0 / 5.0

Subtask #2 0 / 8.0

Subtask #3 6.0 / 6.0

Subtask #4 0 / 6.0

Subtask #5 0 / 12.0

Subtask #6 0 / 32.0

Subtask #7 0 / 31.0

Subtask #1
0 / 5.0

Subtask #2
0 / 8.0

Subtask #3
6.0 / 6.0

Subtask #4
0 / 6.0

Subtask #5
0 / 12.0

Subtask #6
0 / 32.0

Subtask #7
0 / 31.0