oj.uz

답안 #264431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
264431 2020-08-14T06:51:14 Z 문홍윤(#5092) 전차 (CEOI13_tram) C++17
0 / 100
 28 ms 4332 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const LL INF=8e18;

int n, q, re, llin[150010], rlin[150010];
bool ch[150010][3];
pii ans[150010];

pair<LL, pii> get_max(int s, int e){
    pair<LL, pii> ret=mp(-INF, mp(-1, -1));
    int x[4]={s, (s+e)/2, (s+e)/2+1, e};
    for(int i=0; i<4; i++){
        if(x[i]>e)continue;
        for(int j=0; j<2; j++){
            LL d=INF;
            for(int i2=0; i2<4; i2+=3){
                for(int j2=0; j2<2; j2++){
                    if(!ch[x[i2]][j2])continue;
                    d=min(d, (LL)(x[i]-x[i2])*(x[i]-x[i2])+(LL)(j-j2)*(j-j2));
                }
            }
            ret=max(ret, mp(d, mp(-x[i], -j)));
        }
    }
    if(ret.F==-1)return mp(INF, mp(-s, 0));
    return ret;
}

set<pair<pair<LL, pii>, pii> > s;

int main(){
    scanf("%d %d", &n, &q);
    pair<pair<LL, pii>, pii> non;
    non.S.F=1, non.S.S=n;
    rlin[1]=n;
    llin[n]=1;
    non.F=get_max(1, n);
    s.insert(non);
    for(int i=1; i<=q; i++){
        char c;
        scanf(" %c", &c);
        if(c=='E'){
            pair<pair<LL, pii>, pii> nw=*s.rbegin();
            s.erase(nw);
            ans[++re]=mp(-nw.F.S.F, -nw.F.S.S);
            rlin[nw.S.F]=ans[re].F;
            llin[nw.S.S]=ans[re].F;
            llin[ans[re].F]=nw.S.F;
            rlin[ans[re].F]=nw.S.S;
            pair<pair<LL, pii>, pii> l, r;
            l.S.F=nw.S.F, l.S.S=ans[re].F;
            r.S.F=ans[re].F, r.S.S=nw.S.S;
            ch[ans[re].F][ans[re].S]=true;
            l.F=get_max(l.S.F, l.S.S);
            r.F=get_max(r.S.F, r.S.S);
            s.insert(l);
            s.insert(r);
        }
        else{
            int num;
            scanf("%d", &num);
            pair<pair<LL, pii>, pii> l, r;
            l.S.F=llin[ans[num].F], l.S.S=ans[num].F;
            r.S.F=ans[num].F, r.S.S=rlin[ans[num].F];
            l.F=get_max(l.S.F, l.S.S);
            r.F=get_max(r.S.F, r.S.S);
            s.erase(l);
            s.erase(r);
            llin[ans[num].F]=0;
            rlin[ans[num].F]=0;
            rlin[l.S.F]=r.S.S;
            llin[r.S.S]=l.S.F;
            ch[ans[num].F][ans[num].S]=false;
            pair<pair<LL, pii>, pii> nw;
            nw.S.F=l.S.F, nw.S.S=r.S.S;
            nw.F=get_max(nw.S.F, nw.S.S);
            s.insert(nw);
        }
    }
    for(int i=1; i<=re; i++)printf("%d %d\n", ans[i].F, ans[i].S+1);
}
/*
3 7
E
E
E
L 2
E
L 1
E
*/

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
tram.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |             scanf("%d", &num);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 15.0

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

Subtask #8
0 / 20.0

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