oj.uz

답안 #657759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
657759 2022-11-11T00:42:38 Z RambaXGorilla 전차 (CEOI13_tram) C++17
100 / 100
 209 ms 15984 KB 
#include<cstdio>
#include<algorithm>
#include<utility>
#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++){
        cands.push_back(lii(sq(inf), ii(max(a, 1), i + 1)));
        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 < 6;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];
    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);
        }
    }
}

Compilation message

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 660 KB Output is correct
2 Correct 7 ms 300 KB Output is correct
3 Correct 7 ms 532 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 7 ms 532 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1060 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 7 ms 544 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 980 KB Output is correct
2 Correct 7 ms 340 KB Output is correct
3 Correct 6 ms 468 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 5356 KB Output is correct
2 Correct 152 ms 972 KB Output is correct
3 Correct 153 ms 3804 KB Output is correct

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 15984 KB Output is correct
2 Correct 148 ms 972 KB Output is correct
3 Correct 157 ms 4952 KB Output is correct