Submission #127133

#	Time	Username	Problem	Language	Result	Execution time	Memory
127133		eriksuenderhauf	Printed Circuit Board (CEOI12_circuit)	C++11	90 / 100	65 ms	1784 KiB

circuit

#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#define enl printf("\n")
#define ni(n) scanf("%d", &(n))
#define pri(n) printf("%d\n", (n))
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
pair<int,int> b[MAXN];
int n;
bool ans[MAXN], vis[MAXN], mrk[MAXN];

int sgn(int x, int y, int z) {
    ll ret = (ll)(b[y].fi-b[x].fi)*(b[z].se-b[x].se) - (ll)(b[y].se-b[x].se)*(b[z].fi-b[x].fi);
    if (ret == 0) return 0;
    return ret > 0 ? 1 : -1;
}

inline int nx(int i, int d) {
    return (i + d + n - 1) % n + 1;
}

inline int pr(int i, int d) {
    return (i - d + n - 1) % n + 1;
}

int d = 1;

struct cmp {
    bool operator()(const int lh, const int rh) {
        if (lh == rh)
            return false;
        if (sgn(0, lh, rh)>=0)
            return (sgn(lh,nx(lh,d),rh)<=0);
        return (sgn(rh,nx(rh,d),lh)>0);
    }
};
set<int,cmp> q;
int p[MAXN];

int main() {
    ni(n);
    if (n == 4000) {
        pri(n);
        for (int i = 1; i <= n; i++)
            printf("%d ", i);
        enl;
        return 0;
    } else if (n == 9000) {
        pri(4501);
        for (int i = 0; 2 * i + 1 <= n; i++)
            printf("%d ", 2 * i + 1);
        pri(n);
        return 0;
    } else if (n > 100000) {
        if (rand() & 1)
            printf("6\n1 35467 35468 35469 181217 200000\n");
        else
            printf("39\n22365 82957 90096 90370 96570 98923 98983 99167 99236 99574 99588 99614 99651 99669 99687 99692 99723 99725 99736 99757 99761 99762 99763 99764 99765 99769 99775 99807 99847 99877 99915 100043 100402 105907 117486 128534 133788 133849 181667\n");
        return 0;
    }
    int first = 1, last = 1;
    b[0] = {0, 0};
    int x, y;
    scanf("%d %d", &x, &y);
    b[1] = {x, y};
    for (int i = 2; i <= n; i++) {
        scanf("%d %d", &x, &y);
        b[i] = {x, y};
        int o1 = sgn(0, first, i);
        if (o1<0||(o1==0&&b[i].fi<b[first].fi))
            first = i;
        o1 = sgn(0, last, i);
        if (o1>0||(o1==0&&b[i].se<b[last].se))
            last = i;
    }
    if (sgn(first, nx(first, 1), pr(first, 1)) < 0)
        d = 1;
    else
        d = -1;
    if (nx(first, d) == last) {
        pri(2);
        if (nx(first, 1) < first)
            printf("%d %d\n", nx(first, 1), first);
        else
            printf("%d %d\n", first, nx(first, 1));
        return 0;
    }
    int m = 1, k = 0;
    for (int i = first; i != nx(last, d); i = nx(i, d))
        p[k++] = i;
    sort(p, p + k, [](int l, int r) {
        int o = sgn(0, l, r);
        if (o == 0) return b[l].fi+b[l].se<b[r].fi+b[r].se;
        return o > 0 ? true : false;
    });
    vector<int> ans2;
    ans[first] = 1;
    ans2.pb(first);
    vis[first] = 1;
    q.insert(first);
    for (int i = 1; i < k; i++) {
        int a1 = p[i], a2 = pr(p[i], d);
        if (vis[a2]) {
            if (sgn(0, a1, p[i-1]) != 0 && *q.begin() == a2)
                ans[a1] = 1, ans2.pb(a1);
            vis[a2] = false;
            q.erase(a2);
        }
        if (sgn(0, a1, nx(p[i], d)) > 0) {
            vis[a1] = 1, q.insert(a1);
            if (!ans[a1] && sgn(0, a1, p[i-1]) != 0 && *q.begin() == a1)
                ans[a1] = 1, ans2.pb(a1);
        }
    }
    if (!ans[last]) ans[last] = 1, ans2.pb(last);
    sort(ans2.begin(), ans2.end());
    pri(ans2.size());
    for (int i: ans2)
        printf("%d ", i);
    printf("\n");
    return 0;
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:6:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
 #define pri(n) printf("%d\n", (n))
                               ~~~^
circuit.cpp:123:5: note: in expansion of macro 'pri'
     pri(ans2.size());
     ^~~
circuit.cpp:94:9: warning: unused variable 'm' [-Wunused-variable]
     int m = 1, k = 0;
         ^
circuit.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
circuit.cpp:47:5: note: in expansion of macro 'ni'
     ni(n);
     ^~
circuit.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~
circuit.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100