Submission #1250236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250236		Geforgs	Towers (NOI22_towers)	C++20	100 / 100	1327 ms	261716 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;
    cin>>n;
    vector<set<ll>> a(dim);
    vector<set<ll>> b(dim);
    vector<pair<ll, ll>> input(n);
    set<ll> check;
    set<pair<ll, ll>> towers;
    for(i=0;i<n;++i){
        cin>>x>>y;
        a[x].insert(y);
        input[i] = {x, y};
    }
    for(i=0;i<dim;++i){
        if(!a[i].empty()){
            x = *a[i].begin();
            b[x].insert(i);
            if(b[x].size() == 3){
                check.insert(x);
            }
            x = *a[i].rbegin();
            b[x].insert(i);
            if(b[x].size() == 3){
                check.insert(x);
            }
        }
    }
    while(!check.empty()){
        y = *check.begin();
        check.erase(check.begin());
        while(b[y].size() > 2){
            auto it = ++b[y].begin();
            if(a[*it].size() > 1){
                a[*it].erase(y);
                i = *it;
                if(*a[*it].begin() < y){
                    x = *a[*it].rbegin();
                }else{
                    x = *a[*it].begin();
                }
                b[x].insert(i);
                if(b[x].size() == 3){
                    check.insert(x);
                }
            }else{
                a[*it].erase(y);
            }
            b[y].erase(it);
        }
    }
    for(i=0;i<dim;++i){
        for(auto el: b[i]){
            towers.insert({el, i});
        }
    }
    for(i=0;i<n;++i){
        if(towers.find(input[i]) == towers.end()){
            cout<<0;
        }else{
            cout<<1;
        }
    }
    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: 31 / 31
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19