oj.uz

Submission #657242

# Submission time Handle Problem Language Result Execution time Memory
657242 2022-11-09T09:57:32 Z RambaXGorilla Tram (CEOI13_tram) C++17
80 / 100
 140 ms 12120 KB 
#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);
        }
    }
}

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Incorrect 6 ms 304 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 676 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 5 ms 468 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 852 KB Output is correct
2 Correct 8 ms 340 KB Output is correct
3 Correct 6 ms 500 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 848 KB Output is correct
2 Incorrect 6 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 5304 KB Output is correct
2 Correct 129 ms 1032 KB Output is correct
3 Correct 117 ms 3612 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12120 KB Output is correct
2 Correct 121 ms 928 KB Output is correct
3 Correct 119 ms 3960 KB Output is correct