답안 #82038 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
82038	2018-10-28T15:00:57 Z	duality	Printed Circuit Board (CEOI12_circuit)	C++11	5 / 100	100 ms	12388 KB

circuit

#define DEBUG 1

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const pair<T1,T2> &p) {
	output << "(" << p.first << "," << p.second << ")";
	return output;
}

int x[100000],y[100000],small[100000];
vector<double> sorted;
pair<pii,pii> tree[1 << 18];
double value(pair<pii,pii> p,double a) {
    pair<double,double> v = mp(1,a);
    double m = sqrt(a*a+1);
    double d1 = (p.first.first*v.first+p.first.second*v.second)/m;
    double c1 = (p.first.second*v.first-p.first.first*v.second)/m;
    double d2 = (p.second.first*v.first+p.second.second*v.second)/m;
    double c2 = (p.second.second*v.first-p.second.first*v.second)/m;
    //printVar(d1),printVar(d2),printVar(c1),printVar(c2);
    return (-c2*d1+c1*d2)/(c1-c2);
}
int comp(pair<pii,pii> a,pair<pii,pii> b,int s,int e) {
    if (b.first.first == -1) return 1;
    double m = (sorted[s]+sorted[e+1])/2;
    return value(a,m) < value(b,m);
}
int update(int s,int e,int as,int ae,int i,pair<pii,pii> p) {
    //if(i==0){
    //    cout<<as<<","<<ae<<","<<p<<endl;
    //}
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        if (comp(p,tree[i],s,e)) tree[i] = p;
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,as,ae,2*i+1,p),update(mid+1,e,as,ae,2*i+2,p);
    return 0;
}
pair<pii,pii> ans[100000];
int query(int s,int e,int q,int i) {
    if ((s > q) || (e < q)) return 0;
    else if (tree[i].first.first != -1) {
        ans[q] = tree[i];
        return 0;
    }

    int mid = (s+e) / 2;
    query(s,mid,q,2*i+1),query(mid+1,e,q,2*i+2);
    return 0;
}
vi sol;
int main() {
    int i;
    int N;
    scanf("%d",&N);
    for (i = 0; i < N; i++) {
        scanf("%d %d",&x[i],&y[i]);
        sorted.pb((double) y[i]/x[i]);
    }
    sort(sorted.begin(),sorted.end());
    sorted.resize(unique(sorted.begin(),sorted.end())-sorted.begin());

    fill(tree,tree+(1 << 18),mp(mp(-1,-1),mp(-1,-1)));
    fill(small,small+sorted.size(),-1);
    for (i = 0; i < N; i++) {
        int p = lower_bound(sorted.begin(),sorted.end(),(double) y[i]/x[i])-sorted.begin();
        int q = lower_bound(sorted.begin(),sorted.end(),(double) y[(i+1) % N]/x[(i+1) % N])-sorted.begin();
        update(0,sorted.size()-2,min(p,q),max(p,q)-1,0,mp(mp(x[i],y[i]),mp(x[(i+1) % N],y[(i+1) % N])));
        if ((small[p] == -1) || (mp(x[i],y[i]) < mp(x[small[p]],y[small[p]]))) small[p] = i;
    }
    //debug "here";
    for (i = 0; i < sorted.size()-1; i++) {
            ans[i] = mp(mp(-1,-1),mp(-1,-1));
    for (int j = 0; j < N; j++) {
        pair<pii,pii> pp = mp(mp(x[j],y[j]),mp(x[(j+1) % N],y[(j+1) % N]));
        int p = lower_bound(sorted.begin(),sorted.end(),(double) y[j]/x[j])-sorted.begin();
        int q = lower_bound(sorted.begin(),sorted.end(),(double) y[(j+1) % N]/x[(j+1) % N])-sorted.begin();
        if ((min(p,q) > i) || (max(p,q)-1 < i)) continue;
        if (comp(pp,ans[i],i,i)) ans[i] = pp;
    }
        //query(0,sorted.size()-2,i,0);
        //cout << ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second.first<<" "<<ans[i].second.second<<endl;
    }
    for (i = 0; i < N; i++) {
        int p = lower_bound(sorted.begin(),sorted.end(),(double) y[i]/x[i])-sorted.begin();
        int l = (p == 0) ? 1:((ans[p-1].first == mp(x[i],y[i])) || (ans[p-1].second == mp(x[i],y[i])));
        int r = (p == sorted.size()-1) ? 1:((ans[p].first == mp(x[i],y[i])) || (ans[p].second == mp(x[i],y[i])));
        if (l && r) sol.pb(i);
        else if ((l || r) && (small[p] == i)) sol.pb(i);
    }
    printf("%d\n",sol.size());
    for (i = 0; i < sol.size(); i++) printf("%d ",sol[i]+1);
    printf("\n");

    return 0;
}

Compilation message

circuit.cpp: In function 'int main()':
circuit.cpp:128:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < sorted.size()-1; i++) {
                 ~~^~~~~~~~~~~~~~~~~
circuit.cpp:143:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         int r = (p == sorted.size()-1) ? 1:((ans[p].first == mp(x[i],y[i])) || (ans[p].second == mp(x[i],y[i])));
                  ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:147:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n",sol.size());
                   ~~~~~~~~~~^
circuit.cpp:148:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < sol.size(); i++) printf("%d ",sol[i]+1);
                 ~~^~~~~~~~~~~~
circuit.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
circuit.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x[i],&y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4552 KB	Output is correct
2	Execution timed out	153 ms	4740 KB	Time limit exceeded
3	Execution timed out	1082 ms	5192 KB	Time limit exceeded
4	Execution timed out	1076 ms	5340 KB	Time limit exceeded
5	Execution timed out	1075 ms	5456 KB	Time limit exceeded
6	Execution timed out	1078 ms	5712 KB	Time limit exceeded
7	Execution timed out	1081 ms	6124 KB	Time limit exceeded
8	Execution timed out	1072 ms	6124 KB	Time limit exceeded
9	Execution timed out	1076 ms	6124 KB	Time limit exceeded
10	Execution timed out	1077 ms	6124 KB	Time limit exceeded
11	Execution timed out	1082 ms	6344 KB	Time limit exceeded
12	Execution timed out	1082 ms	6752 KB	Time limit exceeded
13	Execution timed out	1071 ms	7328 KB	Time limit exceeded
14	Execution timed out	1084 ms	7972 KB	Time limit exceeded
15	Execution timed out	1077 ms	8952 KB	Time limit exceeded
16	Execution timed out	1070 ms	11020 KB	Time limit exceeded
17	Execution timed out	1075 ms	12248 KB	Time limit exceeded
18	Execution timed out	41 ms	12248 KB	Time limit exceeded (wall clock)
19	Execution timed out	31 ms	12248 KB	Time limit exceeded (wall clock)
20	Execution timed out	39 ms	12388 KB	Time limit exceeded (wall clock)

답안 #82038

Compilation message

Subtask #1 5.0 / 100.0

Subtask #1
5.0 / 100.0