oj.uz

답안 #54018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54018 2018-07-02T08:27:14 Z tmwilliamlin168 전차 (CEOI13_tram) C++14
60 / 100
 412 ms 14956 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second

const int mxN=1e5, mxM=3e4;
int n, m, p[mxM];
set<int> ors, av;
bool occ[mxN][2];

inline pli d2(int a) {
	if(ors.size()<=1)
		return pli();
	int b=*ors.upper_bound(a);
	if(a==-1)
		return {(ll)b*b+(!occ[b][0]||!occ[b][1]), occ[b][0]&&!occ[b][1]};
	if(b==n)
		return {(ll)(n-1-a)*(n-1-a)+(!occ[a][0]||!occ[a][1]), 2*(n-1)+(occ[a][0]&&!occ[a][1])};
	ll d=b-a;
	if(d%2==0) {
		if(!(occ[a][0]&&occ[b][1])&&!(occ[a][1]&&occ[b][0]))
			return {(d/2)*(d/2)+1, 2*((a+b)/2)+occ[a][0]};
		return {(d/2)*(d/2), 2*((a+b)/2)};
	}
	int os=occ[a][0]+occ[a][1]+occ[b][0]+occ[b][1];
	if(os!=3)
		return {(d/2)*(d/2)+(os==2), 2*((a+b)/2)+(os==2&&occ[a][0])};
	return {(d/2)*(d/2)+1, 2*((a+b)/2+(occ[a][0]&&occ[a][1]))+(occ[a][0]&&occ[b][0])};
}

struct asicmp {
	inline bool operator()(const int &a, const int &b) const {
		ll da=d2(a).fi, db=d2(b).fi;
		return da==db?a<b:da>db;
	}
};
set<int, asicmp> asis;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	ors.insert(-1);
	ors.insert(n);
	for(int i=0; i<2*n; ++i)
		av.insert(i);
	asis.insert(-1);
	for(int mi=0; mi<m; ++mi) {
		char qt;
		cin >> qt;
		if(qt=='E') {
			p[mi]=*asis.begin();
			pli ad=d2(p[mi]);
			if(ad.fi<=1)
				p[mi]=*av.begin();
			else
				p[mi]=ad.se;
			av.erase(p[mi]);
			auto it=ors.lower_bound(p[mi]/2);
			asis.erase(*--it);
			asis.erase(p[mi]/2);
			occ[p[mi]/2][p[mi]%2]=1;
			ors.insert(p[mi]/2);
			asis.insert(*it);
			asis.insert(p[mi]/2);
			cout << p[mi]/2+1 << " " << p[mi]%2+1 << endl;
//			for(auto it2=asis.begin(); it2!=asis.end(); ++it2)
//				cout << *it2 << " " << d2(*it2).fi << " " << d2(*it2).se << endl;
		} else {
			int pk;
			cin >> pk, --pk;
			auto it=ors.lower_bound(p[pk]/2);
			asis.erase(*--it);
			asis.erase(p[pk]/2);
			occ[p[pk]/2][p[pk]%2]=0;
			if(occ[p[pk]/2][0]||occ[p[pk]/2][1])
				asis.insert(p[pk]/2);
			else
				ors.erase(p[pk]/2);
			asis.insert(*it);
			av.insert(p[pk]);
		}
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 620 KB Output is correct
2 Correct 9 ms 364 KB Output is correct
3 Correct 11 ms 492 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 620 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Correct 10 ms 492 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 14804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 14828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 2600 KB Output is correct
2 Correct 250 ms 620 KB Output is correct
3 Correct 279 ms 2668 KB Output is correct

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 412 ms 14956 KB Output isn't correct
2 Halted 0 ms 0 KB -