Submission #521418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521418	2022-02-02T05:54:27 Z	amunduzbaev	IOI Fever (JOI21_fever)	C++14	6 / 100	1 ms	588 KB

fever

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 2>> p(n);
	for(int i=0;i<n;i++) cin>>p[i][0]>>p[i][1];
	map<int, deque<int>> m1, m2, x, y;
	for(int i=0;i<n;i++){
		m1[p[i][0] + p[i][1]].push_back(i);
		m2[p[i][0] - p[i][1]].push_back(i);
	}
	
	for(auto& [x, v] : m1){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
		//~ for(int i=0;i<(int)v.size();i++) p1[v[i]] = i;
	}
	
	for(auto& [x, v] : m2){
		sort(v.begin(), v.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
		//~ for(int i=0;i<(int)v.size();i++) p2[v[i]] = i;
	}
	
	int ans = 0;
	for(int t=0;t<4;t++){
		auto t1 = m1, t2 = m2;
		vector<int> T(n, 2e9); T[0] = 0;
		priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> qq; qq.push({0, t, 0});
		int res = 0;
		while(!qq.empty()){
			res++;
			auto u = qq.top(); qq.pop();
			int i = u[2], t = u[1];
			if(u[0] > T[i]) continue;
			{
				auto& v = m1[p[i][0] + p[i][1]];
				while(!v.empty()){
					if(t == 0){
						int x = v.front();
						if(p[i][0] - p[x][0] < T[i]) break;
						v.pop_front();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 1, x});
						}
					} if(t == 1){
						int x = v.back();
						if(p[x][0] - p[i][0] < T[i]) break;
						v.pop_back();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 0, x});
						}
					} if(t == 2){
						int x = v.back();
						if(p[x][0] - p[i][0] < T[i]) break;
						v.pop_back();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 3, x});
						}
					} if(t == 3){
						int x = v.front();
						if(p[i][0] - p[x][0] < T[i]) break;
						v.pop_front();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 2, x});
						}
					}
				}
			}
			
			{
				auto& v = m2[p[i][0] - p[i][1]];
				while(!v.empty()){
					if(t == 0){
						int x = v.back();
						if(p[x][0] - p[i][0] < T[i]) break;
						v.pop_back();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 3, x});
						}
					} if(t == 1){
						int x = v.back();
						if(p[x][0] - p[i][0] < T[i]) break;
						v.pop_back();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 2, x});
						}
					} if(t == 2){
						int x = v.front();
						if(p[i][0] - p[x][0] < T[i]) break;
						v.pop_front();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 1, x});
						}
					} if(t == 3){
						int x = v.front();
						if(p[i][0] - p[x][0] < T[i]) break;
						v.pop_front();
						if(T[x] > abs(p[i][0] - p[x][0])){
							T[x] = abs(p[i][0] - p[x][0]);
							qq.push({T[x], 0, x});
						}
					}
				}
			}
			
			//~ if(!u1.count(p[i][0] + p[i][1])){
				//~ if(v.back() == i && (d == 1 || d == 2));
				//~ else if(v[0] == i && (d == 0 || d == 3));
				//~ else {
					//~ int dd = (d < 2 ? 1 : 2);
					//~ for(auto x : v){
						//~ if(x == i) dd = (d < 2 ? 0 : 3);
						//~ if(used[x]) continue;
						//~ used[x] = 1;
						//~ qq.push({x, dd});
					//~ }
					//~ u1.insert(p[i][0] + p[i][1]);
				//~ }
			//~ }
			
			//~ if(!u2.count(p[i][0] - p[i][1])){
				//~ auto& v = m2[p[i][0] - p[i][1]];
				//~ if(v.back() == i && (d == 0 || d == 1));
				//~ else if(v[0] == i && (d == 2 || d == 3));
				//~ else {
					//~ int dd = (d == 0 || d == 3 ? 0 : 1);
					//~ for(auto x : v){
						//~ if(x == i) dd = (dd == 0 ? 3 : 2);
						//~ if(used[x]) continue;
						//~ used[x] = 1;
						//~ qq.push({x, dd});
					//~ }
					//~ u2.insert(p[i][0] - p[i][1]);
				//~ }
			//~ }
		}
		
		ans = max(ans, res);
		m1 = t1, m2 = t2;
	}
	
	cout<<ans<<"\n";
}

Compilation message

fever.cpp: In function 'int main()':
fever.cpp:19:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for(auto& [x, v] : m1){
      |            ^
fever.cpp:24:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |  for(auto& [x, v] : m2){
      |            ^

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	0 ms	312 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	312 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	0 ms	312 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	312 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	440 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	1 ms	460 KB	Output is correct

Subtask #4
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	0 ms	312 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	312 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	0 ms	312 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	312 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #6
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	0 ms	312 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	312 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Subtask #7
0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	324 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	0 ms	312 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	312 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Incorrect	0 ms	204 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

Submission #521418

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