Submission #1302347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302347		mr_fin	Towers (NOI22_towers)	C++20	22 / 100	258 ms	71840 KiB

Main

#include <bits/stdc++.h>

#define tl      5007
#define nl      1000007


#define fi first
#define se second
#define sz() size()


#define ll long long
#define ps push_back
#define vi vector<int>
#define pii pair<int,int>
#define vpi vector<pair<int,int>>


using namespace std;


mt19937_64 rd(time(0));
long long Random( long long l , long long r ) { return l + rd() % (r-l+1) ; }


int n;
struct lamp{ int x, y, id; } a[nl];

void Input() {

    cin >> n;
    for( int i = 1 ; i <= n ; i ++ )
        cin >> a[i].x >> a[i].y, a[i].id = i;
}



namespace Sub2 {

    bool p[22];
    bool ck() {

        for( int i = 1 ; i <= n ; i ++ ) {

            if(p[i] == 1) continue;

            int xa = 0, xb = 0;
            int ya = 0, yb = 0;
            for( int j = 1 ; j <= n ; j ++ ) if(p[j]) {

                if(a[j].y == a[i].y) {

                    xa += (a[j].x < a[i].x);
                    xb += (a[j].x > a[i].x);
                }

                if(a[j].x == a[i].x) {

                    ya += (a[j].y < a[i].y);
                    yb += (a[j].y > a[i].y);
                }
            }
            if( min(xa,xb) == 0 && min(ya,yb) == 0 ) return false;
        }

        for( int i = 1 ; i <= n ; i ++ ) if(p[i]) {

            int cntx = 0;
            int cnty = 0;
            for( int j = 1 ; j <= n ; j ++ )
            if(j != i && p[j]) {

                cntx += a[i].x == a[j].x;
                cnty += a[i].y == a[j].y;
            }
            if(max(cntx,cnty) >= 2) return false;
        }

        return true;
    }

    void Solve() {

        for( int mask = 1; mask < (1<<n) ; mask ++ ) {

            for( int i = 0 ; i < n ; i ++ )
                p[i+1] = (mask>>i)&1;

            if(ck()) {

                for( int i = 1 ; i <= n ; i ++ ) cout << p[i];
                break;
            }
        }
    }
}



namespace Sub3 {

    bool OK() {

        vi cnt(nl,0);
        for( int i = 1 ; i <= n ; i ++ ) cnt[a[i].x] ++;
        for( int i = 1 ; i <= nl-7 ; i ++ )
            if(cnt[i] > 2) return false;
        return true;
    }

    void Solve() {

        sort(a+1,a+1+n, [&]( lamp u, lamp v){

            if(u.y == v.y) return u.x < v.x;
            return u.y < v.y;
        });

        vi p(n+3,0);

        p[a[1].id] = 1;
        for( int i = 2 ; i <= n+1 ; i ++ )
        if(a[i].y > a[i-1].y || i > n) {
            p[a[i-1].id] = p[a[i].id] = 1;
        }

        for( int i = 1 ; i <= n ; i ++ )
            cout << p[i];
    }
}

unordered_map<int,bool> vs[nl];
void Test() {

    ofstream out("SLAMP.inp");

    int N = 10;
    out << N << '\n';

    vector<bool> cnt(nl,0);


    int mx = nl-7;
    for( int i = 1 ; i <= N ; i += 2 ) {

        int x = Random(1,mx);
        while(cnt[x] == 1) x = Random(1,mx);

        int v = Random(1,mx);
        while(vs[x][v] == 1) v = Random(1,mx);
        out << x << ' ' << v << '\n';
        vs[x][v] = true;

        while(vs[x][v] == 1) v = Random(1,mx);
        out << x << ' ' << v << '\n';
        vs[x][v] = true;
        cnt[x] = 1;
    }
}

 int main() {

    #define Beta "SLAMP"
    if( fopen( Beta ".INP", "r" ) ){

        freopen( Beta ".INP", "r", stdin )  ;
        freopen( Beta ".OUT", "w", stdout ) ;
    }

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //Test();
    Input();


    if(n <= 20) Sub2::Solve();
    else        Sub3::Solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen( Beta ".INP", "r", stdin )  ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen( Beta ".OUT", "w", stdout ) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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