| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 264745 |
2020-08-14T08:56:39 Z |
반딧불(#5094) |
Tram (CEOI13_tram) |
C++17 |
|
1000 ms |
1004 KB |
#include <bits/stdc++.h>
#define SQR(x) ((x)*(x))
using namespace std;
typedef long long ll;
int n, m, p;
ll x[150002], y[150002];
int idx[150002];
bool occupied[150002][3];
struct dat{
ll l, r, v;
bool cmp;
dat* opp = nullptr;
dat(){}
dat(ll l, ll r, ll v, bool cmp): l(l), r(r), v(v), cmp(cmp){}
bool operator<(const dat &t)const{
if(!cmp) return v==t.v?(l==t.l?r<t.r:l<t.l):v>t.v;
return l<t.l;
}
ll recalculate(){
v = 0;
if(occupied[l][1] ^ occupied[l][2]) v = 1;
if(occupied[r][1] ^ occupied[r][2]) v = 1;
ll tmp = (l + r) / 2;
for(int i=1; i<=2; i++){
for(int j=1; j<=2; j++){
if(occupied[l][i] && !occupied[tmp][j]) v = max(v, SQR(tmp - l) + SQR(j - i));
if(occupied[r][i] && !occupied[tmp+1][j]) v = max(v, SQR(tmp+1 - r) + SQR(j - i));
}
}
if((occupied[l][1] || occupied[l][2]) ^ (occupied[r][1] || occupied[r][2])){
v = SQR(r-l) + 1;
}
return v;
}
pair<ll, ll> location(){
v = 0;
pair<ll, ll> ret (1LL, 1LL);
if(occupied[l][1] ^ occupied[l][2]) v = 1, ret = {l, occupied[l][1] ? 2 : 1};
else if(occupied[r][1] ^ occupied[r][2]) v = 1, ret = {r, occupied[r][1] ? 2 : 1};
vector<ll> vec {(l+r)/2, (l+r)/2+1, l, r};
for(auto &tmp: vec){
for(ll i=1; i<=2; i++){
if(occupied[tmp][i]) continue;
ll tdist = 1e18;
for(ll j=1; j<=2; j++){
if(occupied[l][j]) tdist = min(tdist, SQR(l - tmp) + SQR(i - j));
if(occupied[r][j]) tdist = min(tdist, SQR(r - tmp) + SQR(i - j));
}
if(v < tdist || (v == tdist && ret > make_pair(tmp, i))) v = tdist, ret = make_pair(tmp, i);
}
}
if(!(occupied[l][1] || occupied[l][2])){
if(occupied[r][2]) v = SQR(r-l)+1, ret = {l, 1};
else if(occupied[r][1]) v = SQR(r-l)+1, ret = {l, 2};
}
else if(!(occupied[r][1] || occupied[r][2])){
if(occupied[l][2]) v = SQR(r-l)+1, ret = {r, 1};
else if(occupied[l][1]) v = SQR(r-l)+1, ret = {r, 2};
}
return ret;
}
};
int main(){
int cnt = 0;
scanf("%d %d", &n, &m);
for(int q=1; q<=m; q++){
char c;
scanf(" %c", &c);
if(c == 'E'){
cnt++;
ll dist = -1;
pair<ll, ll> ans;
vector<ll> v;
for(int i=1; i<=n; i++){
if(i==1 || i==n || occupied[i][1] || occupied[i][2]) v.push_back(i);
}
for(int i=0; i<(int)v.size()-1; i++){
dat tmp = dat(v[i], v[i+1], 0, 0);
if(tmp.recalculate() > dist){
dist = tmp.v;
ans = tmp.location();
}
}
x[q] = ans.first, y[q] = ans.second;
occupied[x[q]][y[q]] = 1;
}
else{
cnt--;
int p;
scanf("%d", &p);
occupied[x[p]][y[p]] = 0;
}
}
for(int i=1; i<=m; i++){
if(x[i]) printf("%lld %lld\n", x[i], y[i]);
}
}
Compilation message
tram.cpp: In function 'int main()':
tram.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
80 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
tram.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
105 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
403 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
411 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1024 ms |
828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
1004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
