제출 #657242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657242		RambaXGorilla	전차 (CEOI13_tram)	C++17	80 / 100	140 ms	12120 KiB

tram

#include<cstdio>
#include<algorithm>
#include<utility>
#include<iterator>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair <int,int> ii;
typedef pair <ll, ii> lii;
const int inf = 1000000000;
int N, M;
ii entries[30010];
set <lii> best;
map <int,set <int>> rows;
ll sq(ll a){
    return a * a;
}
vector <lii> calc(int a, int b){
    vector <lii> cands;
    for(int i = 0;i < 2;i++){
        for(int j = 1;j < 3;j++){
            cands.push_back(lii(sq(inf), ii(max(min((a + b) / 2 + i, N), 1), j)));
        }
    }
    int nums[] = {a, b};
    for(int i = 0;i < 4;i++){
        for(int j = 0;j < 2;j++){
            for(int k : rows[nums[j]]){
                cands[i].first = min(cands[i].first, sq(cands[i].second.first - nums[j]) + sq(cands[i].second.second - k));
            }
        }
    }
    return cands;
}
void merge(int a, int b){
    vector <lii> cands = calc(a, b);
    for(lii i : cands){
        i.first *= -1;
        best.insert(i);
    }
}
void split(int a, int b){
    vector <lii> cands = calc(a, b);
    for(lii i : cands){
        i.first *= -1;
        best.erase(i);
    }
}
int main(){
    rows[-inf];
    rows[inf + 2];
    best.insert(lii(-sq(inf), ii(1, 1)));
    scanf("%d %d\n",&N,&M);
    for(int i = 1;i < M + 1;i++){
        char a;
        scanf("%c",&a);
        if(a == 'E'){
            scanf("\n");
            ii place = best.begin()->second;
            entries[i] = place;
            split((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first);
            split((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first);
            rows[place.first].insert(place.second);
            merge((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first);
            merge((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first);
            printf("%d %d\n",place.first,place.second);
        }
        else{
            int b;
            scanf(" %d\n",&b);
            ii place = entries[b];
            split((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first);
            split((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first);
            rows[place.first].erase(place.second);
            if(rows[place.first].empty()){
                rows.erase(place.first);
            }
            merge((--rows.upper_bound(place.first))->first, rows.upper_bound(place.first)->first);
            merge((--rows.lower_bound(place.first))->first, rows.lower_bound(place.first)->first);
        }
    }
}

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

tram.cpp: In function 'int main()':
tram.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d %d\n",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%c",&a);
      |         ~~~~~^~~~~~~~~
tram.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf("\n");
      |             ~~~~~^~~~~~
tram.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf(" %d\n",&b);
      |             ~~~~~^~~~~~~~~~~~

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