Submission #127122

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

circuit

#pragma GCC optimize("Ofast")
#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;
    }
    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;
    }
    int x1 = nx(first, 1);
    int x2 = pr(first, 1);
    if (sgn(first, x1, x2) < 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:5: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:118:5: note: in expansion of macro 'pri'
     pri(ans2.size());
     ^~~
circuit.cpp:89:9: warning: unused variable 'm' [-Wunused-variable]
     int m = 1, k = 0;
         ^
circuit.cpp:4: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:46:5: note: in expansion of macro 'ni'
     ni(n);
     ^~
circuit.cpp:63: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:66: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