제출 #34065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34065		imaxblue	경계 (BOI14_demarcation)	C++14	0 / 100	13 ms	4012 KiB

demarcation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, p, t, sgn, x[100005], y[100005], bit[100005];
vector<pair<int, pii> > v, w;
map<int, int> m, m2;
set<int> s;
ll c, ar, len;
void add(int P){
    for (P=m[P]; P<=100000; P+=P&-P) bit[P]++;
}
int sum(int P, int V=0){
    for (P=m[P]-1; P>0; P-=P&-P) V+=bit[P]; return V;
}
void flip(int X, int Y){
    if (s.count(X)){
        sgn=1; s.erase(X);
    } else {
        sgn=0; s.insert(X);
    }
    if (s.count(Y)) s.erase(Y);
    else s.insert(Y);
    if ((sum(X)+sgn)%2==0){
        len+=Y-X;
    } else {
        len+=X-Y;
    }
    add(X); add(Y);
}
int main(){
    scanf("%i", &n);
    fox(l, n){
        scanf("%i%i", &x[l], &y[l]);
        m[y[l]]=0;
        m2[x[l]]=0;
    }
    p=0; for (map<int, int>::iterator i=m.begin(); i!=m.end(); ++i) m[i->x]=++p;//, cout << i->x << ' ';
    p=0; for (map<int, int>::iterator i=m2.begin(); i!=m2.end(); ++i) m2[i->x]=++p;
    //cout << endl;
    x[n]=x[0]; y[n]=y[0];
    fox(l, n){
        if (x[l]==x[l+1]){
            v.pb(mp(x[l], mp(min(y[l], y[l+1]), max(y[l], y[l+1]))));
        }
        if (y[l]==y[l+1]){
            w.pb(mp(y[l], mp(min(x[l], x[l+1]), max(x[l], x[l+1]))));
        }
    }
    sort(v.begin(), v.end());
    sort(w.begin(), w.end());
    fox(l, v.size()-1){
        flip(v[l].y.x, v[l].y.y);
        c+=len*(v[l+1].x-v[l].x);
        // cout << v[l].y.x << ' ' << v[l].y.y << ' ' << len << ' ' << c<< endl;
    }
    //return 0;
    ar=c;
    if (ar%2!=0){
        cout << "NO";
        return 0;
        //impossible
    }
    c=0; len=0; drain(bit); s.clear();
    fox(l, v.size()-1){
        flip(v[l].y.x, v[l].y.y);
        if (c*2<ar && 2*(c+len*(v[l+1].x-v[l].x))>=ar){
            if (s.size()==2 && (c+len*(v[l+1].x-v[l].x)-ar/2)%len==0){
                t=v[l+1].x-(c+len*(v[l+1].x-v[l].x)-ar/2)/len;
                printf("%i %i %i %i", t, *s.begin(), t, *++s.begin());
                return 0;
            }
            //break;
        }
        c+=len*(v[l+1].x-v[l].x);
        //cout << len << ' ' << c << endl;
    }
    len=0; c=0; s.clear(); m=m2; drain(bit);
    fox(l, w.size()-1){
        flip(w[l].y.x, w[l].y.y);
        if (c*2<ar && 2*(c+len*(w[l+1].x-w[l].x))>=ar){
            if (s.size()==2 && (c+len*(w[l+1].x-w[l].x)-ar/2)%len==0){
                t=w[l+1].x-(c+len*(w[l+1].x-w[l].x)-ar/2)/len;
                printf("%i %i %i %i", *s.begin(), t, *++s.begin(), t);
                return 0;
            }
            //break;
        }
        //cout << len << endl;
        c+=len*(w[l+1].x-w[l].x);
    }
    //fail
    cout << "NO";
    return 0;
}
/*
10
0 0
1 0
1 1
3 1
3 7
2 7
2 4
1 4
1 3
0 3
*/

컴파일 시 표준 에러 (stderr) 메시지

demarcation.cpp: In function 'int main()':
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
demarcation.cpp:74:5: note: in expansion of macro 'fox'
     fox(l, v.size()-1){
     ^
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
demarcation.cpp:87:5: note: in expansion of macro 'fox'
     fox(l, v.size()-1){
     ^
demarcation.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
demarcation.cpp:101:5: note: in expansion of macro 'fox'
     fox(l, w.size()-1){
     ^
demarcation.cpp:54:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &n);
                    ^
demarcation.cpp:56:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", &x[l], &y[l]);
                                    ^

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 23
• Subtask 4: 0 / 50