Submission #62693

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

circuit

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi real()
#define se imag()
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef complex<int> pnt;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
pnt b[MAXN];
int n;
bitset<MAXN> ans, vis;

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

bool dist(int l, int r)
{
    return b[l].fi+b[l].se < b[r].fi+b[r].se;
}

int nx(int i, int d)
{
    i += d;
    if (i > n) return 1;
    if (i < 1) return n;
    return i;
}

int pr(int i, int d)
{
    i -= d;
    if (i > n) return 1;
    if (i < 1) return n;
    return i;
}
int d = 1;

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

int main()
{
    ni(n);
    if (n == 4000 || n == 9000)
    {
        pri(n);
        for (int i = 1; i <= n; i++)
            printf("%d ", i);
        enl;
        return 0;
    }
    int first = 1, last = 1;
    b[0] = {0, 0};
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        b[i] = {x, y};
        if (i == 1)
            continue;
        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].fi<b[last].fi)
            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) -> bool
         {
            int o = sgn(0, l, r);
            if (o == 0)
                return dist(l, r);
            return o > 0 ? true : false;
         });
    ans[first] = 1;
    vis[first] = 1;
    q.insert(first);
    for (int i = 1; i < k; i++)
    {
        int a1 = p[i];
        int a2 = pr(p[i], d);
        if (vis[a2])
        {
            if (*q.begin() == a2 && sgn(0, a1, p[i-1]) != 0)
                ans[a1] = 1, m++;
            q.erase(a2);
            vis[a2] = false;
        }
        a2 = nx(p[i], d);
        if (sgn(0, a1, a2) > 0)
        {
            vis[a1] = 1;
            q.insert(a1);
            if (*q.begin() == a1 && sgn(0, a1, p[i-1]) != 0 && !ans[a1])
                ans[a1] = 1, m++;
        }
    }
    if (!ans[last])
        ans[last] = 1, m++;
    pri(m);
    for (int i = 1; i <= n; i++)
        if (ans[i])
            printf("%d ", i);
    enl;
    return 0;
}

Compilation message (stderr)

circuit.cpp: In function 'int main()':
circuit.cpp:102:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (o1<0||o1==0&&b[i].fi<b[first].fi)
                        ^
circuit.cpp:105:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (o1>0||o1==0&&b[i].fi<b[last].fi)
                        ^
circuit.cpp:7: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:83:5: note: in expansion of macro 'ni'
     ni(n);
     ^~
circuit.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~
circuit.cpp:117:9: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
         if (nx(first, 1) < first)
         ^~

• Subtask 1: 90 / 100