제출 #493883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493883		hohohaha	Zvijezda (COCI19_zvijezda)	C++14	110 / 110	185 ms	9524 KiB

zvijezda

// #pragma GCC optimize("Ofast")
// #pragma GCC targt("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
   fastio();
   
   int tc = 1;
   
//   cin >> tc; 
   
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

//const ld pi = 4 * atan(1.0), eps = 1e-9;

#define int long long
//#define ll long long
const int maxn = 2e5 + 5, mod = 1e9 + 7; 

int type; 

int n, q, rep; 

ii arr[maxn << 1]; 

#define ld long double

int cv(int x) { 
	if(!x) return 0; 
	if(x < 0) return -1; 
	return 1; 
}

int cw(ii a, ii b, ii c) { 
//	b.fi -= a.fi, c.fi -= a.fi; 
//	b.se -= a.se, c.se -= a.se; 
//	
//	int a1 = cv(b.fi) * cv(c.se), a2 = cv(b.se) * cv(c.fi); 
//	
//	if(!a1 or !a2) return a1 < a2; 
//	
//	return (ld) b.fi * (c.se / abs(c.se)) / abs(c.fi) < (ld) b.se * (c.fi / abs(c.fi)) / abs(c.se); 
	return (double)a.fi * (b.se - c.se) + (double)b.fi * (c.se - a.se) + (double)c.fi * (a.se - b.se) < 0;	
}

void solve() { 	
//	cout << cw(ii(0, 0), ii(0, 1), ii(1, 0)) << endl;

	cin >> type; 
	cin >> n; 
	fori(i,1, n) { 
		cin >> arr[i].fi >> arr[i].se; 
		arr[i + n] = arr[i]; 
	}
	
	cin >> q; 
	
	fori(i,1, q) { 
	 	int x, y; 
	 	cin>> x >> y; 
	 	x = x ^ (type * rep * rep * rep); 
	 	y = y ^ (type * rep * rep * rep); 
	 	
	 	int lo = 2, hi = n; 
	 	
	 	ii qr(x, y); 
	 	
	 	while(lo < hi) { 
	 		int mi = lo + hi + 1 >> 1; 
	 		
	 		if((cw(qr, arr[1], arr[2]) ^ cw(qr, arr[1],arr[mi])) == 0 ) { 
	 			lo = mi;
	 		}
	 		else { 
	 			hi = mi - 1; 
	 		}
	 	}
	 	
	 	int temp = lo; 
	 	
	 	lo = 2, hi = temp; 
	 	
	 	while(lo < hi) { 
	 		int mi = lo + hi >> 1; 
	 		if((cw(qr, arr[1], arr[2]) ^ cw(qr, arr[mi], arr[mi + 1]) ) == 1) { 
	 		 	hi = mi; 
	 		 }
	 		 else {
	 		 	lo = mi + 1; 
	 		 }
	 	}
	 	
	 	int ll = lo; 
	 	
	 	int rr; 
	 	
	 	if(temp == n) { 
	 		rr = 1; 
	 	}
	 	else {
		 	lo = temp + 1, hi = n; 
		 	while(lo < hi) { 
		 	 	int mi = lo + hi >> 1; 
		 	 	if((cw(qr, arr[1], arr[2]) ^ cw(qr, arr[mi], arr[mi + 1]) ) == 0) { 
		 	 		hi = mi; 
		 	 	}
		 	 	else { 
		 	 		lo = mi + 1;
		 	 	}
		 	 }
		 	rr = lo; 
		}
	 	
	 	
	 	if(cw(qr, arr[1], arr[2])) swap(ll, rr); 
	 	 
	 	 if(rr < ll) rr += n; 
	 	 
	 	 if(rr - ll < n / 2) cout << "DA", ++rep; 
	 	 else cout << "NE";
		  
		cout << endl;  
	}
}

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

zvijezda.cpp: In function 'void solve()':
zvijezda.cpp:121:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |     int mi = lo + hi + 1 >> 1;
      |              ~~~~~~~~^~~
zvijezda.cpp:136:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |     int mi = lo + hi >> 1;
      |              ~~~^~~~
zvijezda.cpp:155:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |       int mi = lo + hi >> 1;
      |                ~~~^~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60