oj.uz

Submission #264072

# Submission time Handle Problem Language Result Execution time Memory
264072 2020-08-14T04:58:18 Z 임성재(#5088) Tram (CEOI13_tram) C++17
25 / 100
 1000 ms 940 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define pre(a) cout << fixed; cout.precision(a);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
int cnt;
pll x[150010];
bool chk[150010][2];

ll dist(int i, int j) {
	return (x[i].fi - x[j].fi) * (x[i].fi - x[j].fi) + (x[i].se - x[j].se) * (x[i].se - x[j].se);
}

ll cost(int a) {
	ll ret = INF;
	for(int i=1; i < a; i++) {
		if(x[i].fi) {
			ret = min(ret, dist(a, i));
		}
	}

	return ret;
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=1; i<=m; i++) {
		string s;
		cin >> s;

		if(s == "E") {
			ll mx = 0;
			pii mxi = mp(1, 0);
			
			for(int j=1; j<=n; j++) {
				if(!chk[j][0]) {
					x[i] = mp(j, 0);
					
					if(cost(i) > mx) {
						mx = cost(i);
						mxi = x[i];
					}

					x[i] = mp(0, 0);
				}
				if(!chk[j][1]) {
					x[i] = mp(j, 1);

					if(cost(i) > mx) {
						mx = cost(i);
						mxi = x[i];
					}

					x[i] = mp(0, 0);
				}

			}

			x[i] = mxi;
			chk[x[i].fi][x[i].se] = true;

			cout << x[i].fi << " " << x[i].se+1 << "\n";
		}
		else {
			int l;
			cin >> l;

			chk[x[l].fi][x[l].se] = false;

			x[l] = mp(0, 0);
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 6 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 732 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 1051 ms 940 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 1052 ms 364 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 1073 ms 528 KB Time limit exceeded
2 Halted 0 ms 0 KB -