제출 #30499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30499		rondojim	전차 (CEOI13_tram)	C++14	45 / 100	1087 ms	3076 KiB

tram

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 150007;
const long long INF = (1e18) + 7;
 
int n,q;
pair < int, int > save[N];
bool have[N][2];
long long dist[N][2];
int sz;
 
inline long long get_dist(pair < int, int > a, pair < int, int > b) {
    return ((a.first-b.first)*1ll*(a.first-b.first) + (a.second-b.second)*1ll*(a.second-b.second));
}
 
inline pair < int, int > enter() {
    if(sz==0) {
        return make_pair(1,0);
    }
 
    int i,j;
    int last0,last1;
    long long max_dist=-INF;
 
    for(i=1;i<=n;i++) {
        for(j=0;j<2;j++) {
            dist[i][j]=INF;
        }
    }
 
    last0=0;
    last1=0;
    for(i=1;i<=n;i++) {
        for(j=0;j<2;j++) if(!have[i][j]) {
            if(last0!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last0,0)));
            if(last1!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last1,1)));
            if(have[i][1-j]) dist[i][j]=1;
        }
        if(have[i][0]) last0=i;
        if(have[i][1]) last1=i;
    }
 
    last0=0;
    last1=0;
    for(i=n;i>=1;i--) {
        for(j=0;j<2;j++) if(!have[i][j]) {
            if(last0!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last0,0)));
            if(last1!=0) dist[i][j]=min(dist[i][j],get_dist(make_pair(i,j),make_pair(last1,1)));
            max_dist=max(max_dist,dist[i][j]);
        }
        if(have[i][0]) last0=i;
        if(have[i][1]) last1=i;
    }
 
    for(i=1;i<=n;i++) {
        for(j=0;j<2;j++) if(!have[i][j]) {
            if(max_dist==dist[i][j]) {
                return make_pair(i,j);
            }
        }
    }
}
 
int main() {
    int i,x;
    char type[4];
    
    scanf("%d %d", &n, &q);
    for(i=1;i<=q;i++) {
        scanf("%s", type);
        if(type[0]=='E') {
            save[i]=enter();
            have[save[i].first][save[i].second]=true;
            printf("%d %d\n", save[i].first, save[i].second+1);
            ++sz;
        }
        else {
            scanf("%d", &x);
            have[save[x].first][save[x].second]=false;
            --sz;
        }
    }
 
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tram.cpp: In function 'int main()':
tram.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |         scanf("%s", type);
      |         ~~~~~^~~~~~~~~~~~
tram.cpp:80:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~
tram.cpp: In function 'std::pair<int, int> enter()':
tram.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
   64 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20