oj.uz

Submission #241094

# Submission time Handle Problem Language Result Execution time Memory
241094 2020-06-22T14:42:57 Z vanic Segway (COI19_segway) C++14
40 / 100
 1000 ms 1912 KB 
#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

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

int v[maxn][3];
vector < int > pos[maxs];
int dio[maxn];
int ispred[maxn];
int ubrz[maxn];
vector < int > ubrzavam;
bool acel[maxs];
int sol[maxn];
bool bio[maxn];

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_back(i);
	}
	int cilj=n;
	int mini;
	bool prog;
	int proslo=0;
	int mjesto;
	int isto;
	vector < pair < double , int > > l;
	while(cilj){
		mini=100;
		for(int i=0; i<300; i++){
			for(int j=0; j<pos[i].size(); j++){
				if(ubrz[pos[i][j]]){
					mini=1;
				}
				else{
					mini=min(mini, v[pos[i][j]][i/100]-dio[pos[i][j]]);
				}
			}
		}
		proslo+=mini;
		for(int i=0; i<300; i++){
			for(int j=0; j<pos[i].size(); j++){
				if(!bio[pos[i][j]]){
					bio[pos[i][j]]=1;
					prog=0;
					if(ubrz[pos[i][j]]){
						prog=1;
						ubrz[pos[i][j]]--;
					}
					else{
						dio[pos[i][j]]+=mini;
						if(dio[pos[i][j]]==v[pos[i][j]][i/100]){
							prog=1;
							dio[pos[i][j]]=0;
						}
					}
					if(prog){
//						ispred[pos[i][j]]-=pos[i+1].size();
						pos[i+1].push_back(pos[i][j]);
						if(!ubrz[pos[i][j]] && acel[i+1]){
							ubrzavam.push_back(pos[i][j]);
						}
						if(i+1==300){
							sol[pos[i][j]]=proslo;
							cilj--;
						}
						pos[i].erase(pos[i].begin()+j);
						j--;
/*						for(int k=0; k<pos[i].size(); k++){
							ispred[pos[i][k]]++;
						}*/
					}
				}
			}
		}
		mjesto=pos[300].size();
//		cout << "proso" << endl;
		for(int i=299; i>=0; i--){
			for(int j=0; j<pos[i].size(); j++){
				l.push_back({(double)dio[pos[i][j]]/v[pos[i][j]][i/100], pos[i][j]});
			}
			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();
		}
//		cout << "dalje" << endl;
		while(!ubrzavam.empty()){
			ubrz[ubrzavam.back()]=ispred[ubrzavam.back()]%20;
			ubrzavam.pop_back();
		}
		for(int i=0; i<n; i++){
			bio[i]=0;
		}
	}
	for(int i=0; i<n; i++){
		cout << sol[i] << '\n';
	}
	return 0;
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<pos[i].size(); j++){
                 ~^~~~~~~~~~~~~~
segway.cpp:62:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<pos[i].size(); j++){
                 ~^~~~~~~~~~~~~~
segway.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<pos[i].size(); j++){
                 ~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 53 ms 384 KB Output is correct
3 Correct 158 ms 632 KB Output is correct
4 Correct 624 ms 760 KB Output is correct
5 Execution timed out 1095 ms 1912 KB Time limit exceeded

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 11 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 17 ms 384 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 23 ms 384 KB Output is correct
8 Correct 30 ms 384 KB Output is correct
9 Correct 30 ms 384 KB Output is correct
10 Correct 46 ms 384 KB Output is correct
11 Correct 14 ms 384 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 53 ms 384 KB Output is correct
3 Correct 158 ms 632 KB Output is correct
4 Correct 624 ms 760 KB Output is correct
5 Execution timed out 1095 ms 1912 KB Time limit exceeded