Submission #1273170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273170		hungeazy	Tram (CEOI13_tram)	C++17	0 / 100	492 ms	102888 KiB

tram

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bit(x,i) ((x) >> (i) & 1)
#define MASK(i) ((1) << (i))
#define set_on(x, i) ((x) |  MASK(i))

int const maxn = 1e6 + 5;

int n, m;

namespace sub1{
    bool mark[1505][3];
    pair<int, int> pre_query[1505];

    double cal_dist(int Ra, int Ca, int Rb, int Cb){
        return (double)(sqrt((Ra - Rb)*(Ra - Rb) + (Ca - Cb)*(Ca - Cb)));
    }

    void solve(){
        memset(mark, false, sizeof(mark));
        int cnt = 0;

        for(int T = 1; T <= m; ++T){
            char type; cin >> type;

            if(type == 'E'){
                if(cnt == 0){
                    ++cnt;
                    mark[1][1] = true;
                    pre_query[T] = make_pair(1, 1);
                    cout << 1 << ' ' << 1 << '\n';
                }
                else{
                    double maxdist = 0;
                    pair<int, int> pos;

                    for(int i = 1; i <= n; ++i){
                        for(int j = 1; j <= 2; ++j){
                            if(mark[i][j] == false){
                                double mindist = 1000000000.0;

                                for(int x = 1; x <= n; ++x){
                                    for(int y = 1; y <= 2; ++y){
                                        if(mark[x][y] == true){
                                            mindist = min(mindist, cal_dist(i, j, x, y));
                                        }
                                    }
                                }

                                cout << i << ' ' << j << ' ' << mindist << endl;

                                if(maxdist < mindist){
                                    maxdist = mindist;
                                    pos.first = i, pos.second = j;
                                }
                            }
                        }
                    }

                    ++cnt;
                    mark[pos.first][pos.second] = true;
                    pre_query[T] = make_pair(pos.first, pos.second);
                    cout << pos.first << ' ' << pos.second << '\n';
                }
            }
            else{
                int id; cin >> id;
                --cnt;
                mark[pre_query[id].first][pre_query[id].second] = false;
            }
        }
    }
}

namespace sub2{
    bool mark[1505][3];
    pair<int, int> pre_query[1501];
    multiset<double> ms[1501][3];

    double cal_dist(int Ra, int Ca, int Rb, int Cb){
        return (double)(sqrt((Ra - Rb)*(Ra - Rb) + (Ca - Cb)*(Ca - Cb)));
    }

    void solve(){
        int cnt = 0;

        for(int T = 1; T <= m; ++T){
            char type; cin >> type;

            if(type == 'E'){
                if(cnt == 0){
                    ++cnt;
                    mark[1][1] = true;
                    pre_query[T] = make_pair(1, 1);

                    for(int i = 1; i <= n; ++i){
                        for(int j = 1; j <= 2; ++j){
                            if(i != 1 && j != 1){
                                ms[i][j].insert(cal_dist(1, 1, i, j));
                            }
                        }
                    }

                    cout << 1 << ' ' << 1 << '\n';
                }
                else{
                    double maxdist = 0;
                    pair<int, int> pos;

                    for(int i = 1; i <= n; ++i){
                        for(int j = 1; j <= 2; ++j){
                            if(mark[i][j] == false){
                                double mindist = *ms[i][j].begin();

                                if(maxdist < mindist){
                                    maxdist = mindist;
                                    pos.first = i, pos.second = j;
                                }
                            }
                        }
                    }

                    for(int i = 1; i <= n; ++i){
                        for(int j = 1; j <= 2; ++j){
                            if(i != pos.first && j != pos.second){
                                ms[i][j].insert(cal_dist(pos.first, pos.second, i, j));
                            }
                        }
                    }

                    ++cnt;
                    mark[pos.first][pos.second] = true;
                    pre_query[T] = make_pair(pos.first, pos.second);
                    cout << pos.first << ' ' << pos.second << '\n';
                }
            }
            else{
                int id; cin >> id;
                int x = pre_query[id].first, y = pre_query[id].second;
                mark[x][y] = false;

                for(int i = 1; i <= n; ++i){
                    for(int j = 1; j <= 2; ++j){
                        if(i != x && j != y){
                            ms[i][j].erase(ms[i][j].lower_bound(cal_dist(i, j, x, y)));
                        }
                    }
                }
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("XLH.INP", "r", stdin);
    // freopen("XLH.OUT", "w", stdout);

    cin >> n >> m;

    if(n <= 150 && m <= 150){
        sub1::solve();
        return 0;
    }


    sub2::solve();

    return 0;
}

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