oj.uz

Submission #63399

# Submission time Handle Problem Language Result Execution time Memory
63399 2018-08-01T16:42:47 Z bazsi700 Tram (CEOI13_tram) C++14
45 / 100
 1000 ms 4468 KB 
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

double dist[150002][3];
bool occ[150002][3];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin >> n >> m;
	map<int,pair<int,int> > pass;
	pair<int,int> mnat = {1,1};
	for(int i = 1; i <= n; i++) {
		dist[i][1] = dist[i][2] = 3000000;
	}
	for(int ev = 1; ev <= m; ev++) {
		char ch;
		cin >> ch;
		if(ch == 'E') {
			mnat = {1,1};
			for(int i = 1; i <= n; i++) {
				for(int c = 1; c <= 2; c++) {
					if(dist[i][c] > dist[mnat.first][mnat.second]+0.000001) {
						mnat = {i,c};
					}
				}
			}
			pass[ev] = mnat;
			cout << mnat.first << " " << mnat.second << "\n";
			occ[mnat.first][mnat.second] = true;
			for(int c = 1; c <= 2; c++) {
				int lastwasat = mnat.first;
				for(int i = mnat.first; i <= n; i++) {
					double dis = sqrt((i-lastwasat)*(i-lastwasat)+(c-mnat.second)*(c-mnat.second));
					if(dist[i][c] < dis-1.5) {
						break;
					}
					dist[i][c] = min(dist[i][c],dis);
				}
				for(int i = mnat.first; i >= 1; i--) {
					double dis = sqrt((i-lastwasat)*(i-lastwasat)+(c-mnat.second)*(c-mnat.second));
					if(dist[i][c] < dis-1.5) {
						break;
					}
					dist[i][c] = min(dist[i][c],dis);
				}
			}
		} else {
			int x;
			cin >> x;
			auto pr = pass[x];
			occ[pr.first][pr.second] = false;
			pass.erase(x);
			int fr = -10;
			int to = n+10;
			for(int i = pr.first; i < n; i++) {
				if(occ[i][1] || occ[i][2]) {
					to = i+4;
					break;
				}
			}
			for(int i = pr.first; i >= 1; i--) {
				if(occ[i][1] || occ[i][2]) {
					fr = i-4;
					break;
				}
			}
			//fr = -10;
		//	to = n+10;
		//	cout << fr << "a" << to << endl;
			for(int i = max(1,fr+2); i <= min(n,to-2); i++) {
				dist[i][1] = dist[i][2] = 3000000;
			}
			for(int c = 1; c <= 2; c++) {
				int lastwasat = -1;
				for(int i = max(1,fr); i <= min(n,to); i++) {
					if(occ[i][c]) {
						lastwasat = i;
					}
					if(lastwasat != -1) {
						dist[i][c] = min(dist[i][c],double(i-lastwasat));
					}
				}
				lastwasat = -1;
				for(int i = min(n,to); i >= max(1,fr); i--) {
					if(occ[i][c]) {
						lastwasat = i;
					}
					if(lastwasat != -1) {
						dist[i][c] = min(dist[i][c],double(lastwasat-i));
					}
				}
			}
			for(int c = 1; c <= 2; c++) {
				int lastwasat = -1;
				for(int i = max(1,fr); i <= min(n,to); i++) {
					if(occ[i][3-c]) {
						lastwasat = i;
					}
					if(lastwasat != -1) {
						dist[i][c] = min(dist[i][c],sqrt((i-lastwasat)*(i-lastwasat)+1));
					}
				}
				lastwasat = -1;
				for(int i = min(n,to); i >= max(1,fr); i--) {
					if(occ[i][3-c]) {
						lastwasat = i;
					}
					if(lastwasat != -1) {
						dist[i][c] = min(dist[i][c],sqrt((i-lastwasat)*(i-lastwasat)+1));
					}
				}
			}
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 20 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 492 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Correct 24 ms 364 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 4332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 4392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 1296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 4468 KB Time limit exceeded
2 Halted 0 ms 0 KB -