oj.uz

Submission #241543

# Submission time Handle Problem Language Result Execution time Memory
241543 2020-06-24T12:02:36 Z vanic Segway (COI19_segway) C++14
40 / 100
 1000 ms 1144 KB 
#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int maxn=2e4+5, maxs=305;

int v[maxn][3];
priority_queue < pair < int, int > > pos[maxs];
//int dio[maxn];
int ispred[maxn];
int ubrz[maxn];
vector < int > ubrzavam;
bool acel[maxs];
int sol[maxn];

int inv(int x){
	return 1e9-x;
}

int main(){
/*+	for(int i=1; i<300; i++){
		printf("%d ", i);
	}
	printf("\n");*/
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	}
	int m;
	cin >> m;
	int a;
	for(int i=0; i<m; i++){
		cin >> a;
		acel[a]=1;
	}
	for(int i=0; i<n; i++){
		pos[0].push({inv(v[i][0]), i});
	}
	int cilj=n;
	int mini;
	bool prog;
	int proslo=0;
	int mjesto;
	int isto;
	int juric=0;
	vector < pair < double , int > > l;
	pair < int, int > p;
	priority_queue < pair < int, int > > q;
	while(cilj){
		if(!juric){
			mini=100;
			for(int i=0; i<300; i++){
				if(!pos[i].empty()){
					mini=min(mini, inv(pos[i].top().first));
				}
			}
		}
		else{
			mini=1;
		}
		proslo+=mini;
//		cout << proslo << '\n';
		for(int i=299; i>-1; i--){
			while(!pos[i].empty()){
				p=pos[i].top();
				pos[i].pop();
				p.first=inv(p.first);
				p.first-=mini;
				if(p.first==0 || ubrz[p.second]){
					if(i+1==300){
//						cout << "CILJ " << p.second << '\n';;
						cilj--;
						sol[p.second]=proslo;
					}
					else if(ubrz[p.second]){
//						cout << "ubrzava " << p.second << endl;
						ubrz[p.second]--;
						p.first=v[p.second][(i+1)/100];
						if(!ubrz[p.second]){
							juric--;
						}
					}
					else{
						p.first=v[p.second][(i+1)/100];
					}
					if(!ubrz[p.second] && acel[i+1]){
						ubrzavam.push_back(p.second);
					}
					pos[i+1].push({inv(p.first), p.second});
				}
				else{
					q.push({inv(p.first), p.second});
				}
			}
			pos[i]=q;
			while(!q.empty()){
				q.pop();
			}
		}
		
		mjesto=pos[300].size();
		for(int i=299; i>=0; i--){
			q=pos[i];
			while(!q.empty()){
				l.push_back({(double)(v[q.top().second][i/100]-inv(q.top().first))/v[q.top().second][i/100], q.top().second});
				q.pop();
			}
			sort(l.begin(), l.end());
			for(int j=l.size()-1; j>-1; j--){
				isto=1;
				while(j-1>-1 && l[j].first==l[j-1].first){
					ispred[l[j].second]=mjesto;
					j--;
					isto++;
				}
				ispred[l[j].second]=mjesto;
				mjesto+=isto;
			}
			l.clear();
		}
		while(!ubrzavam.empty()){
			ubrz[ubrzavam.back()]=ispred[ubrzavam.back()]%20;
			if(ubrz[ubrzavam.back()]){
				juric++;
			}
			ubrzavam.pop_back();
		}
	}
	for(int i=0; i<n; i++){
		cout << sol[i] << '\n';
	}
	return 0;
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:47:7: warning: unused variable 'prog' [-Wunused-variable]
  bool prog;
       ^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 104 ms 384 KB Output is correct
3 Correct 406 ms 760 KB Output is correct
4 Execution timed out 1089 ms 1144 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 27 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 29 ms 384 KB Output is correct
6 Correct 10 ms 384 KB Output is correct
7 Correct 43 ms 384 KB Output is correct
8 Correct 52 ms 384 KB Output is correct
9 Correct 54 ms 384 KB Output is correct
10 Correct 91 ms 480 KB Output is correct
11 Correct 20 ms 504 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 104 ms 384 KB Output is correct
3 Correct 406 ms 760 KB Output is correct
4 Execution timed out 1089 ms 1144 KB Time limit exceeded
5 Halted 0 ms 0 KB -