제출 #34065

#제출 시각아이디문제언어결과실행 시간메모리
34065imaxblue경계 (BOI14_demarcation)C++14
0 / 100
13 ms4012 KiB
#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]);
                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...