Submission #1273074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273074		hungeazy	Tram (CEOI13_tram)	C++17	45 / 100	758 ms	205472 KiB

tram

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define se second
#define bit(x,i) (((x) >> (i)) & 1)
#define MASK(i) (1 << i)
#define set_on(x,i) ((x)  MASK(i))
#define set_off(x,i) ((x) & ~MASK(i))
#define fast ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int mod = 1e9 + 7; //998244353;
const int base = 311;
const int maxn = 1e5 + 5;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int dx8[] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy8[] = {0, 1, 0, -1, 1, -1, 1, -1};

int n, m;

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

    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);
                    cout << 1 << ' ' << 1 << '\n';
                }
                else{
                    pair<int, int> pos;
                    double maxdist = 0;

                    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));
                                        }
                                    }
                                }

                                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].se] = false;
            }
        }
    }
}

namespace sub2{
    bool mark[1510][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){
                                continue;
                            }

                            ms[i][j].insert(cal_dist(i, j, 1, 1));
                        }
                    }

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

                    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){
                                continue;;
                            }

                            ms[i][j].insert(cal_dist(i, j, pos.first, pos.second));
                        }
                    }

                    ++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;
                int x = pre_query[id].first, y = pre_query[id].second;

                for(int i = 1; i <= n; ++i){
                    for(int j = 1; j <= 2; ++j){
                        if(i == x && j == y){
                            continue;
                        }

                        ms[i][j].erase(ms[i][j].lower_bound(cal_dist(x, y, i, j)));
                    }
                }

                mark[pre_query[id].first][pre_query[id].se] = false;
            }
        }
    }
}

int main()
{
    fast

    cin >> n >> m;

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

    sub2::solve();

    return 0; 
}

• 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