oj.uz

Submission #61850

# Submission time Handle Problem Language Result Execution time Memory
61850 2018-07-26T21:41:33 Z Benq Printed Circuit Board (CEOI12_circuit) C++11
25 / 100
 100 ms 24748 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

// library

pi operator+(const pi& l, const pi& r) { return {l.f+r.f,l.s+r.s}; }
pi operator+=(pi& l, const pi& r) { return l = l+r; }

void prin(pair<pi,pi> x) {
    cout << x.f.f << " " << x.f.s << " " << x.s.f << " " << x.s.s << "\n----\n";
}

ld cross(cd a, cd b) { return (conj(a)*b).imag(); }
ld area(cd a, cd b, cd c) { return cross(b-a,c-a); }
ld dot(cd a, cd b) { return (conj(a)*b).real(); }

cd reflect(cd p, cd a, cd b) { return a+conj((p-a)/(b-a))*(b-a); }
cd proj(cd p, cd a, cd b) { return (p+reflect(p,a,b))/(ld)2; }

cd line(cd a, cd b, cd c, cd d) {
    ld x = area(a,b,c), y = area(a,b,d);
    return (x*d-y*c)/(x-y);
}

ld eval(pair<pi,pi> x, pi y) {
    return norm(line(cd(x.f.f,x.f.s),cd(x.s.f,x.s.s),cd(y.f,y.s),cd(0,0)));
}

int N, rv[MX];
vi ev[MX][2], v, ans;
pi p[MX]; 

// 1, b: ins
// b, a, -1: del 
// a, 0, 0: query

bool equiv(pi a, pi b) { return (ll)a.f*b.s == (ll)a.s*b.f; }

bool cmp(pi a, pi b) {
    if (equiv(a,b)) return a < b;
    return (ll)a.s*b.f < (ll)b.s*a.f;
}

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) cin >> p[i].f >> p[i].s;
    FOR(i,1,N+1) v.pb(i);
    sort(all(v),[](int a, int b) { return cmp(p[a],p[b]); });
    F0R(i,N) rv[v[i]] = i;
    
    FOR(i,1,N+1) {
        int a = i, b = i%N+1;
        if (rv[a] > rv[b]) swap(a,b);
        if (!equiv(p[a],p[b])) {
            ev[b][0].pb(a);
            ev[a][1].pb(b);
        }
    }
}

pi cur;

struct CMP {
    bool operator()(const pair<pi,pi>& l, const pair<pi,pi>& r) {
        if (cur == mp(-1,-1)) {
            /*cout << "OOPS\n";
            prin(l);
            prin(r);
            exit(0);*/
            if (l.s == cur) return norm(cd(l.f.f,l.f.s)) < eval(r,l.f);
            if (r.s == cur) return eval(l,r.f) < norm(cd(r.f.f,r.f.s));
            exit(5);
        } else {
            return eval(l,cur) < eval(r,cur);
        }
    }
};

set<pair<pi,pi>,CMP> S;

void del(int l, int r) {
    if (l == 0) return;
    FOR(i,l,r+1)  for (int j: ev[v[i]][0]) S.erase({p[j],p[v[i]]});
}

void tri(int l, int r) {
    cur = {-1,-1};
    if (S.lb({p[v[l]],cur}) == S.begin()) ans.pb(v[l]);
}

void ins(int l, int r) {
    if (r == sz(v)-1) return;
    cur = p[v[r]]+p[v[r+1]];
    FOR(i,l,r+1) for (int j: ev[v[i]][1]) S.insert({p[v[i]],p[j]});
}

void answer(int l, int r) {
    del(l,r);
    tri(l,r);
    ins(l,r);
}

int main() {
    init();
    for (int i = 0; i < sz(v); ) {
        int I = i;
        while (i < sz(v) && equiv(p[v[I]],p[v[i]])) i ++;
        answer(I,i-1);
    }
    
    cout << sz(ans) << "\n";
    sort(all(ans));
    for (int i: ans) cout << i << " ";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 13 ms 5232 KB Output is correct
3 Correct 15 ms 5584 KB Output is correct
4 Correct 17 ms 5752 KB Output is correct
5 Execution timed out 118 ms 6080 KB Time limit exceeded
6 Execution timed out 119 ms 6500 KB Time limit exceeded
7 Execution timed out 293 ms 7360 KB Time limit exceeded
8 Correct 95 ms 7360 KB Output is correct
9 Execution timed out 116 ms 7360 KB Time limit exceeded
10 Execution timed out 124 ms 7360 KB Time limit exceeded
11 Execution timed out 126 ms 7360 KB Time limit exceeded
12 Execution timed out 139 ms 8004 KB Time limit exceeded
13 Execution timed out 364 ms 9184 KB Time limit exceeded
14 Execution timed out 413 ms 9960 KB Time limit exceeded
15 Execution timed out 367 ms 11280 KB Time limit exceeded
16 Execution timed out 733 ms 15576 KB Time limit exceeded
17 Execution timed out 1077 ms 17796 KB Time limit exceeded
18 Runtime error 67 ms 19572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 60 ms 22044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 24748 KB Execution killed with signal 11 (could be triggered by violating memory limits)