Submission #1012932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012932		Unforgettablepl	IOI Fever (JOI21_fever)	C++17	100 / 100	964 ms	53588 KiB

fever

#include <bits/stdc++.h>
using std::vector;
using std::max;
using std::map;
using std::tuple;
using std::cout;
using std::cin;
using std::pair;
using std::priority_queue;
using std::make_pair;
using std::lower_bound;
using std::upper_bound;
 
#define x first
#define y second

#define int long long

enum dire{
    down,
    right,
    up,
    left,
};

enum lines{
    downR,
    downL,
    downC,
    leftR,
    leftL,
    leftC,
    rightR,
    rightL,
    rightC,
    upL,
    upR,
    upC,
    base,
};

int process(vector<pair<int,int>> points){
    int n = points.size();
    vector<dire> direction(n);
    direction[0] = up;
    for(int i=1;i<n;i++){
        if(points[i].y>0 and points[i].y>abs(points[i].x))direction[i]=down;
        else if(points[i].y<0 and points[i].y<=-abs(points[i].x))direction[i]=up;
        else if(points[i].x>=0 and points[i].x>=abs(points[i].y))direction[i]=left;
        else direction[i]=right;
    }
    vector<map<int,vector<pair<int,int>>>> lists(12);
    for(int i=0;i<n;i++){
        if(direction[i]==down){
            lists[downL][points[i].x+points[i].y].emplace_back(-points[i].x,i);
            lists[downR][points[i].x-points[i].y].emplace_back(points[i].x,i);
            lists[downC][points[i].x].emplace_back(points[i].y,i);
        } else if(direction[i]==right){
            lists[rightL][points[i].x+points[i].y].emplace_back(-points[i].x,i);
            lists[rightR][points[i].x-points[i].y].emplace_back(-points[i].x,i);
            lists[rightC][points[i].y].emplace_back(-points[i].x,i);
        } else if(direction[i]==up){
            lists[upL][points[i].x+points[i].y].emplace_back(points[i].x,i);
            lists[upR][points[i].x-points[i].y].emplace_back(-points[i].x,i);
            lists[upC][points[i].x].emplace_back(-points[i].y,i);
        } else if(direction[i]==left){
            lists[leftL][points[i].x+points[i].y].emplace_back(points[i].x,i);
            lists[leftR][points[i].x-points[i].y].emplace_back(points[i].x,i);
            lists[leftC][points[i].y].emplace_back(points[i].x,i);
        }
    }
    for(auto&a:lists){
        auto iter = a.begin();
        while(iter!=a.end()){
            sort(iter->second.begin(),iter->second.end());
            iter++;
        }
    }
    priority_queue<tuple<int,int,int>> q;
    int ans = 0;
    vector<vector<bool>> visited(n,vector<bool>(13));
    q.emplace(0,0,base);
    while(!q.empty()){
        auto [dist,idx,type] = q.top();q.pop();dist=-dist;
        if(visited[idx][type])continue;
        visited[idx][type]=true;
        if(type==base){
            ans++;
            if(direction[idx]==down){
                {
                    // upC calculation
                    auto iter = lower_bound(lists[upC][points[idx].x].begin(),lists[upC][points[idx].x].end(),make_pair(2ll*dist-points[idx].y,0ll));
                    if(iter!=lists[upC][points[idx].x].end() and !visited[iter->second][upC])q.emplace(-abs(points[idx].y-points[iter->second].y)/2ll,iter->second,upC);
                }
                {
                    // rightR calculation
                    auto iter = lower_bound(lists[rightR][points[idx].x-points[idx].y].begin(),lists[rightR][points[idx].x-points[idx].y].end(),make_pair(dist-points[idx].x,0ll));
                    if(iter!=lists[rightR][points[idx].x-points[idx].y].end() and !visited[iter->second][rightR])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,rightR);
                }
                {
                    // leftL calculation
                    auto iter = lower_bound(lists[leftL][points[idx].x+points[idx].y].begin(),lists[leftL][points[idx].x+points[idx].y].end(),make_pair(dist+points[idx].x,0ll));
                    if(iter!=lists[leftL][points[idx].x+points[idx].y].end() and !visited[iter->second][leftL])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,leftL);
                }
            } else if(direction[idx]==right){
                {
                    // leftC calculation
                    auto iter = lower_bound(lists[leftC][points[idx].y].begin(),lists[leftC][points[idx].y].end(),make_pair(2ll*dist+points[idx].x,0ll));
                    if(iter!=lists[leftC][points[idx].y].end() and !visited[iter->second][leftC])q.emplace(-abs(points[idx].x-points[iter->second].x)/2ll,iter->second,leftC);
                }
                {
                    // downR calculation
                    auto iter = lower_bound(lists[downR][points[idx].x-points[idx].y].begin(),lists[downR][points[idx].x-points[idx].y].end(),make_pair(dist+points[idx].x,0ll));
                    if(iter!=lists[downR][points[idx].x-points[idx].y].end() and !visited[iter->second][downR])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,downR);
                }
                {
                    // upL calculation
                    auto iter = lower_bound(lists[upL][points[idx].x+points[idx].y].begin(),lists[upL][points[idx].x+points[idx].y].end(),make_pair(dist+points[idx].x,0ll));
                    if(iter!=lists[upL][points[idx].x+points[idx].y].end() and !visited[iter->second][upL])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,upL);
                }
            } else if(direction[idx]==up){
                {
                    // downC calculation
                    auto iter = lower_bound(lists[downC][points[idx].x].begin(),lists[downC][points[idx].x].end(),make_pair(2ll*dist+points[idx].y,0ll));
                    if(iter!=lists[downC][points[idx].x].end() and !visited[iter->second][downC])q.emplace(-abs(points[idx].y-points[iter->second].y)/2ll,iter->second,downC);
                }
                {
                    // leftR calculation
                    auto iter = lower_bound(lists[leftR][points[idx].x-points[idx].y].begin(),lists[leftR][points[idx].x-points[idx].y].end(),make_pair(dist+points[idx].x,0ll));
                    if(iter!=lists[leftR][points[idx].x-points[idx].y].end() and !visited[iter->second][leftR])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,leftR);
                }
                {
                    // rightL calculation
                    auto iter = lower_bound(lists[rightL][points[idx].x+points[idx].y].begin(),lists[rightL][points[idx].x+points[idx].y].end(),make_pair(dist-points[idx].x,0ll));
                    if(iter!=lists[rightL][points[idx].x+points[idx].y].end() and !visited[iter->second][rightL])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,rightL);
                }
            } else if(direction[idx]==left){
                {
                    // rightC calculation
                    auto iter = lower_bound(lists[rightC][points[idx].y].begin(),lists[rightC][points[idx].y].end(),make_pair(2ll*dist-points[idx].x,0ll));
                    if(iter!=lists[rightC][points[idx].y].end() and !visited[iter->second][rightC])q.emplace(-abs(points[idx].x-points[iter->second].x)/2ll,iter->second,rightC);
                }
                {
                    // upR calculation
                    auto iter = lower_bound(lists[upR][points[idx].x-points[idx].y].begin(),lists[upR][points[idx].x-points[idx].y].end(),make_pair(dist-points[idx].x,0ll));
                    if(iter!=lists[upR][points[idx].x-points[idx].y].end() and !visited[iter->second][upR])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,upR);
                }
                {
                    // downL calculation
                    auto iter = lower_bound(lists[downL][points[idx].x+points[idx].y].begin(),lists[downL][points[idx].x+points[idx].y].end(),make_pair(dist-points[idx].x,0ll));
                    if(iter!=lists[downL][points[idx].x+points[idx].y].end() and !visited[iter->second][downL])q.emplace(-abs(points[idx].x-points[iter->second].x),iter->second,downL);
                }
            }
        }
        if(!visited[idx][base])q.emplace(-dist,idx,base);
        auto helper = [&](int sum,int val,bool flag=false){
            auto iter = upper_bound(lists[type][sum].begin(),lists[type][sum].end(),make_pair(val,idx));
            if(flag){
                if(iter!=lists[type][sum].end() and !visited[iter->second][type])q.emplace(-((iter->first-val)/2ll+dist),iter->second,type);
            }
            else if(iter!=lists[type][sum].end() and !visited[iter->second][type])q.emplace(-(iter->first-val+dist),iter->second,type);
        };
        switch(type){
            case downL:
                helper(points[idx].x+points[idx].y,-points[idx].x);
                break;
            case downR:
                helper(points[idx].x-points[idx].y,points[idx].x);
                break;
            case downC:
                helper(points[idx].x,points[idx].y,true);
                break;
            case rightL:
                helper(points[idx].x+points[idx].y,-points[idx].x);
                break;
            case rightR:
                helper(points[idx].x-points[idx].y,-points[idx].x);
                break;
            case rightC:
                helper(points[idx].y,-points[idx].x,true);
                break;
            case upL:
                helper(points[idx].x+points[idx].y,points[idx].x);
                break;
            case upR:
                helper(points[idx].x-points[idx].y,-points[idx].x);
                break;
            case upC:
                helper(points[idx].x,-points[idx].y,true);
                break;
            case leftL:
                helper(points[idx].x+points[idx].y,points[idx].x);
                break;
            case leftR:
                helper(points[idx].x-points[idx].y,points[idx].x);
                break;
            case leftC:
                helper(points[idx].y,points[idx].x,true);
                break; 
        }
    }
    return ans;
}


vector<pair<int,int>> rotate(vector<pair<int,int>> points){
    vector<pair<int,int>> ans;
    for(auto&[a,b]:points)ans.emplace_back(-b,a);
    return ans;
}
 
int32_t main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int,int>> points(n);
    for(auto&[a,b]:points){cin>>a>>b;a*=2;b*=2;}
    int offset_x = -points[0].x;
    int offset_y = -points[0].y;
    for(auto&[a,b]:points){a+=offset_x;b+=offset_y;}
    int ans = process(points);
    points = rotate(points);
    ans = max(ans,process(points));
    points = rotate(points);
    ans = max(ans,process(points));
    points = rotate(points);
    ans = max(ans,process(points));
    cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31