| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 385324 | 2021-04-04T05:10:10 Z | mohamedsobhi777 | 전차 (CEOI13_tram) | C++14 | 1000 ms | 876 KB |
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound
using ll = long long;
using ld = long double;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
int n, m;
int vis[N][2];
int xs[N], ys[N];
multiset<int> mul;
struct cmp
{
bool operator()(pii x, pii y)
{
return x.s - x.f != y.s - y.f ? x.s - x.f > y.s - y.f : x.f < y.f;
}
};
set<pii, cmp> st;
set<pii> rst;
int calc(int x, int y)
{
int ret = 1e9;
if (mul.empty())
return ret;
auto eval = [&](int u) -> void {
for (int i = 0; i < 2; ++i)
{
if (vis[u][i])
{
ret = min(ret, (u - x) * (u - x) + (i - y) * (i - y));
}
}
};
auto it = mul.lb(x);
if (it != mul.end())
eval(*it);
if (it != mul.begin())
eval(*(--it));
return ret;
}
void Insert(int x, int y)
{
st.insert({x, y});
rst.insert({x, y});
}
void Erase(int x, int y)
{
st.erase({x, y});
rst.erase({x, y});
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
cin >> n >> m;
Insert(0, n - 1);
for (int i = 0; i < m; ++i)
{
char c;
cin >> c;
if (c == 'E')
{
int Min = 0;
int wx = 0, wy = 0;
if (sz(mul) >= 2 && sz(rst))
{
for (auto u : st)
{
int x = u.f, y = u.s;
int mid = (x + y) >> 1;
for (int j = mid - 1; j <= mid + 1; ++j)
for (int i = 0; i < 2; ++i)
{
if (j < 0 || j >= n)
continue;
int w = calc(j, i);
if (w > Min)
{
Min = w;
wx = j, wy = i;
}
}
}
if (Min <= 2)
{
Min = 0;
for (int a = 0; a < n; ++a)
{
for (int b = 0; b < 2; ++b)
{
int rv = calc(a, b);
if (rv > Min || (rv == Min && make_pair(a, b) < make_pair(wx, wy)))
{
wx = a, wy = b;
Min = rv;
}
}
}
}
}
else if (!sz(rst))
{
wx = sz(mul) - n;
wy = calc(wx, 1) > calc(wx, 0);
if (1)
{
Min = 0;
for (int a = 0; a < n; ++a)
{
for (int b = 0; b < 2; ++b)
{
int rv = calc(a, b);
if (rv > Min || (rv == Min && make_pair(a, b) < make_pair(wx, wy)))
{
wx = a, wy = b;
Min = rv;
}
}
}
}
}
else if (sz(mul) == 1)
wx = n - 1, wy = 1;
xs[i] = wx, ys[i] = wy;
vis[wx][wy] = 1;
for (auto u : st)
{
if (wx >= u.f && wx <= u.s)
{
int x = u.f, y = u.s;
Erase(x, y);
if (x <= wx - 1)
Insert(x, wx - 1);
if (wx + 1 <= y)
Insert(wx + 1, y);
break;
}
}
mul.insert(wx);
cout << ++wx << " " << ++wy << "\n";
}
else
{
int p;
cin >> p;
--p;
mul.erase(mul.find(xs[p]));
vis[xs[p]][ys[p]] = 0;
rst.clear(), st.clear();
int lst = -1;
for (int j = 0; j < n; ++j)
{
if (vis[j][0] || vis[j][1])
{
if (lst + 1 <= j - 1)
Insert(lst + 1, j - 1);
lst = j;
}
}
if (lst + 1 < n)
Insert(lst + 1, n - 1);
continue;
if (vis[xs[p]][0] == vis[xs[p]][1])
{
auto it = rst.lb({xs[p], -1});
int nxt = (it != rst.end() ? (*it).s : n - 1);
if (it != rst.end())
Erase((*it).f, (*it).s);
int prv = xs[p];
if (it != rst.begin())
{
prv = (*--it).f;
Erase((*it).f, (*it).s);
}
Insert(prv, nxt);
}
}
}
return 0;
}
/*
01:*
02: #
03:
04:*
05:
06:
07:*
08:
09:
10: #
*/
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 347 ms | 748 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 377 ms | 492 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1093 ms | 876 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 |
| 2 | Halted | 0 ms | 0 KB | - |