제출 #1250122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250122		Geforgs	Towers (NOI22_towers)	C++20	29 / 100	1764 ms	261496 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

void solve(){
    ll n, i, x, y, dim=1e6+7, tx, ty;
    cin>>n;
    vector<set<ll>> a(dim);
    vector<set<ll>> b(dim);
    vector<bool> aLeft(dim);
    vector<bool> aRight(dim);
    vector<bool> bLeft(dim);
    vector<bool> bRight(dim);
    set<pair<ll, ll>> towers;
    set<pair<ll, ll>> nextTowers;
    vector<pair<ll, ll>> input(n);
    for(i=0;i<n;++i){
        cin>>x>>y;
        a[x].insert(y);
        b[y].insert(x);
        input[i] = {x, y};
    }
    for(i=0;i<dim;++i){
        if(!a[i].empty()){
            if(*b[*a[i].begin()].begin() == i or *b[*a[i].begin()].rbegin() == i){
                x = i;
                y = *a[i].begin();
                if(*a[x].begin() == y){
                    aLeft[x] = true;
                }
                if(*a[x].rbegin() == y){
                    aRight[x] = true;
                }
                if(*b[y].begin() == x){
                    bLeft[y] = true;
                }
                if(*b[y].rbegin() == x){
                    bRight[y] = true;
                }
                nextTowers.insert({x, y});
            }
            if(*b[*a[i].rbegin()].begin() == i or *b[*a[i].rbegin()].rbegin() == i){
                x = i;
                y = *a[i].rbegin();
                if(*a[x].begin() == y){
                    aLeft[x] = true;
                }
                if(*a[x].rbegin() == y){
                    aRight[x] = true;
                }
                if(*b[y].begin() == x){
                    bLeft[y] = true;
                }
                if(*b[y].rbegin() == x){
                    bRight[y] = true;
                }
                nextTowers.insert({x, y});
            }
        }
    }
    while(!nextTowers.empty()){
        tx = nextTowers.begin()->first;
        ty = nextTowers.begin()->second;
        nextTowers.erase({tx, ty});
        towers.insert({tx, ty});
        a[tx].erase(ty);
        if(aLeft[tx] and aRight[tx]){
            for(auto el: a[tx]){
                b[el].erase(tx);
                if(!b[el].empty()){
                    if(!bLeft[el] and ((!aLeft[*b[el].begin()] and *a[*b[el].begin()].begin() == el) or (!aRight[*b[el].begin()] and *a[*b[el].begin()].rbegin() == el))){
                        x = *b[el].begin();
                        y = el;
                        if(*a[x].begin() == y){
                            aLeft[x] = true;
                        }
                        if(*a[x].rbegin() == y){
                            aRight[x] = true;
                        }
                        if(*b[y].begin() == x){
                            bLeft[y] = true;
                        }
                        if(*b[y].rbegin() == x){
                            bRight[y] = true;
                        }
                        nextTowers.insert({x, y});
                    }
                    if(!bRight[el] and ((!aLeft[*b[el].rbegin()] and *a[*b[el].rbegin()].begin() == el) or (!aRight[*b[el].rbegin()] and *a[*b[el].rbegin()].rbegin() == el))){
                        x = *b[el].rbegin();
                        y = el;
                        if(*a[x].begin() == y){
                            aLeft[x] = true;
                        }
                        if(*a[x].rbegin() == y){
                            aRight[x] = true;
                        }
                        if(*b[y].begin() == x){
                            bLeft[y] = true;
                        }
                        if(*b[y].rbegin() == x){
                            bRight[y] = true;
                        }
                        nextTowers.insert({x, y});
                    }
                }
            }
            a[tx].clear();
        }
        b[ty].erase(tx);
        if(bLeft[ty] and bRight[ty]){
            for(auto el: b[ty]){
                a[el].erase(ty);
                if(!a[el].empty()){
                    if(!aLeft[el] and ((!bLeft[*a[el].begin()] and *b[*a[el].begin()].begin() == el) or (!bRight[*a[el].begin()] and *b[*a[el].begin()].rbegin() == el))){
                        x = el;
                        y = *a[el].begin();
                        if(*a[x].begin() == y){
                            aLeft[x] = true;
                        }
                        if(*a[x].rbegin() == y){
                            aRight[x] = true;
                        }
                        if(*b[y].begin() == x){
                            bLeft[y] = true;
                        }
                        if(*b[y].rbegin() == x){
                            bRight[y] = true;
                        }
                        nextTowers.insert({x, y});
                    }
                    if(!aRight[el] and ((!bLeft[*a[el].rbegin()] and *b[*a[el].rbegin()].begin() == el) or (!bRight[*a[el].rbegin()] and *b[*a[el].rbegin()].rbegin() == el))){
                        x = el;
                        y = *a[el].rbegin();
                        if(*a[x].begin() == y){
                            aLeft[x] = true;
                        }
                        if(*a[x].rbegin() == y){
                            aRight[x] = true;
                        }
                        if(*b[y].begin() == x){
                            bLeft[y] = true;
                        }
                        if(*b[y].rbegin() == x){
                            bRight[y] = true;
                        }
                        nextTowers.insert({x, y});
                    }
                }
            }
        }
    }
    for(i=0;i<n;++i){
        if(towers.find(input[i]) != towers.end()){
            cout<<1;
        }else{
            cout<<0;
        }
    }
    cout<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19