oj.uz

Submission #493883

# Submission time Handle Problem Language Result Execution time Memory
493883 2021-12-13T09:48:15 Z hohohaha Zvijezda (COCI19_zvijezda) C++14
110 / 110
 185 ms 9524 KB 
// #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;  
	}
}

Compilation message

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 76 ms 576 KB Output is correct
13 Correct 83 ms 4444 KB Output is correct
14 Correct 100 ms 4988 KB Output is correct
15 Correct 115 ms 5432 KB Output is correct
16 Correct 169 ms 8780 KB Output is correct
17 Correct 166 ms 8776 KB Output is correct
18 Correct 83 ms 4636 KB Output is correct
19 Correct 120 ms 5560 KB Output is correct
20 Correct 146 ms 7012 KB Output is correct
21 Correct 163 ms 8760 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3520 KB Output is correct
2 Correct 145 ms 3588 KB Output is correct
3 Correct 109 ms 5612 KB Output is correct
4 Correct 173 ms 9504 KB Output is correct
5 Correct 185 ms 9524 KB Output is correct
6 Correct 148 ms 8804 KB Output is correct
7 Correct 164 ms 8828 KB Output is correct
8 Correct 153 ms 9428 KB Output is correct
9 Correct 152 ms 8444 KB Output is correct