oj.uz

Submission #966531

# Submission time Handle Problem Language Result Execution time Memory
966531 2024-04-20T03:04:18 Z Darren0724 Fun Tour (APIO20_fun) C++17
0 / 100
 121 ms 16716 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){
				last=3-last-mx.second;
				ans.push_back(pq[last].top().second);
				pq[last].pop();	
				i++;
			}
			//assert(last!=mx.second);
				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 2004 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 1 ms 2000 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 2004 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 1 ms 2000 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 1628 KB Output is correct
3 Correct 1 ms 1616 KB Output is correct
4 Correct 1 ms 2000 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 1628 KB Output is correct
3 Correct 1 ms 1488 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 1 ms 2004 KB Output is correct
8 Correct 1 ms 2004 KB Output is correct
9 Correct 1 ms 1628 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 2256 KB Output is correct
13 Correct 2 ms 1984 KB Output is correct
14 Correct 9 ms 3284 KB Output is correct
15 Correct 108 ms 16400 KB Output is correct
16 Correct 121 ms 16716 KB Output is correct
17 Correct 20 ms 5332 KB Output is correct
18 Correct 49 ms 8736 KB Output is correct
19 Incorrect 82 ms 13276 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 2004 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1616 KB Output is correct
5 Correct 1 ms 2000 KB Output is correct
6 Incorrect 1 ms 2004 KB Tour is not fun
7 Halted 0 ms 0 KB -