oj.uz

Submission #966525

# Submission time Handle Problem Language Result Execution time Memory
966525 2024-04-20T03:01:07 Z Darren0724 Fun Tour (APIO20_fun) C++17
0 / 100
 130 ms 16608 KB 
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int N=100005;
int cntid=0;
const int INF=1e9;
vector<int> ans;
priority_queue<pair<int,int>> pq[4];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
vector<int> createFunTour(int n, int q) {
	ans.clear();
	int c1=0;
	int need=(n+1)/2;
	int mn=INF;
	for(int i=0;i<n-1;i++){
		int t=attractionsBehind(0, i);
		if(t>=need&&t<mn){
			mn=t;
			c1=i;
		}
	}
	vector<int> r;
	vector<int> dis0(N,0);
	for(int i=0;i<n;i++){
		dis0[i]=hoursRequired(c1,i);
		if(dis0[i]==1){
			r.push_back(i);
		}
	}
	int rsz=r.size()-1;
	assert(rsz<=2);
	vector<vector<int>> dis(rsz,vector<int>(N));
	vector<int> vis(N);
	for(int i=0;i<rsz;i++){
		for(int j=0;j<n;j++){
			dis[i][j]=hoursRequired(r[i],j);
		}
	}
	for(int i=0;i<n;i++){
		if(i==c1)continue;
		int p=-1;
		for(int j=0;j<rsz;j++){
			if(dis[j][i]<dis0[i]){
				p=j;break;
			}
		}
		if(p==-1)p=rsz;
		pq[p].push({dis0[i],i});
	}
	cntid=4;
	int last=0;
	int left=n-1;
	for(int i=1;i<n;i++){
		array<int,3> p={-1,-1,-1};
		for(int j=0;j<cntid;j++){
			if(j==last||pq[j].size()==0)continue;
			p=max(p,array<int,3>{pq[j].top().first,(int)pq[j].size(),j});
		}
		pair<int,int> mx={-1,-1};
		for(int j=0;j<cntid;j++){
			mx=max(mx,{(int)pq[j].size(),j});
		}
		if((left-mx.first)<=mx.first){
			if(last!=mx.second&&(!pq[last].empty()&&!pq[3-last-mx.second].empty())&&pq[last].top().first<pq[3-last-mx.second].top().first){;}
			//assert(last!=mx.second);
			else{;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
				p[2]=mx.second;
			}
		}

		last=(p[2]==-1?last:p[2]);
		//assert(last!=-1&&pq[last].size()>0);
		auto [dis1,idx]=pq[last].top();
		pq[last].pop();
		ans.push_back(idx);
		left--;
	}
	ans.push_back(c1);
	/*for(int j:ans){
		cout<<j<<' ';
	}
	cout<<endl;*/
  	return ans;
}
/*
46 100000
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
0 16
16 17 
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
0 31
31 32
31 33
32 34
32 35
33 36
33 37
34 38
34 39
35 40
35 41
36 42 
36 43
37 44
37 45
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2000 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 2004 KB Output is correct
6 Incorrect 1 ms 2004 KB Tour is not fun
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2000 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 2004 KB Output is correct
6 Incorrect 1 ms 2004 KB Tour is not fun
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 2004 KB Output is correct
5 Incorrect 1 ms 2004 KB Tour is not fun
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 2004 KB Output is correct
5 Correct 1 ms 2004 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 2 ms 1968 KB Output is correct
8 Correct 1 ms 2000 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 2004 KB Output is correct
11 Correct 1 ms 2000 KB Output is correct
12 Correct 1 ms 2004 KB Output is correct
13 Correct 2 ms 2004 KB Output is correct
14 Correct 12 ms 3284 KB Output is correct
15 Correct 112 ms 16608 KB Output is correct
16 Correct 130 ms 16456 KB Output is correct
17 Correct 20 ms 5332 KB Output is correct
18 Correct 51 ms 8720 KB Output is correct
19 Incorrect 87 ms 13464 KB Tour is not fun
20 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2000 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 2004 KB Output is correct
6 Incorrect 1 ms 2004 KB Tour is not fun
7 Halted 0 ms 0 KB -