Submission #1294594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294594		chaitanyamehta	Towers (NOI22_towers)	C++20	0 / 100	576 ms	71896 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

bool cmp(pair<int , int> a , pair<int , int> b){
    return a.second < b.second;
}

signed main(){
    int n;cin>>n;
    vector<pair<int , int>> t(n);
    vector<int> pos_x(1e6 + 1) , pos_y(1e6+1);

    for(int i = 0 ; i < n; i++){
        int x , y;
        cin>>x>>y;
        t[i] = {x , y};
        pos_x[x]++;
        pos_y[y]++;
    }

    vector<int> built_x(1e6+1 , 0) , built_y(1e6+1 , 0);
    vector<pair<int , int>> ot;

    for(int i = 0 ; i< n ;i++){
        int x = t[i].first , y = t[i].second;
        int temp = max(0LL , pos_x[x]-1);
        temp += max(0LL , pos_y[y] - 1);
        ot.push_back({temp , i});
    }
    sort(ot.begin() , ot.end());
    
    vector<int> ans(n);
    for(int i = 0 ; i < n ;i++){
        int idx = ot[i].second;
        int opt = ot[i].first;
        int x = t[i].first;
        int y = t[i].second;

        if(built_x[x] >= 2 || built_y[y] >= 2) continue;

        built_x[x]++;
        built_y[y]++;
        ans[idx] = 1;
    }
    for(int i = 0 ; i < n ; i++){
        cout<<ans[i];
    }
}

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