oj.uz

Submission #296634

# Submission time Handle Problem Language Result Execution time Memory
296634 2020-09-10T17:46:18 Z crackersamdjam Mixture (BOI20_mixture) C++17
0 / 100
 2000 ms 256 KB 
#include <bits/stdc++.h>
#define difs(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

#ifndef LOCAL
#define ONLINE_JUDGE
#endif

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
#define pr //
// template<typename... Args>
// void pr(Args... args){}
#endif

using namespace std;
using ld = double;
const int MM = 1e5+5;
const ld pi = acos(-1), eps = 1e-9;

int n, ptr, cnt;
ld x[MM], y[MM];
multiset<ld> angs, difs;
multiset<pair<ld, ld>> pts;

void up(ld f, ld s, bool b){
	ld dif = s-f;
	pr("dif", dif, b);
	if(dif < -eps)
		dif += 2*pi;
	if(b)
		difs.insert(dif);
	else
		difs.erase(difs.lower_bound(dif-eps));
}

int main(){
#ifdef CLION
	freopen("../in", "r", stdin);
#endif
	int a, b, c;
	scan(a, b, c, n);
	x[0] = (ld)a/(a+b+c);
	y[0] = (ld)b/(a+b+c);
	pr("pi", pi);
	pr("init", a, b, c, x[0], y[0]);
	
	for(int t = 0,i; t < n; t++){
		if(gc == 'A'){
			scan(a, b, c);
			i = ++ptr;
			x[i] = (ld)a/(a+b+c)-x[0];
			y[i] = (ld)b/(a+b+c)-y[0];
			pr("ins", a, b, c, x[i], y[i]);
			pts.insert({x[i], y[i]});
			ld ang = atan2(y[i], x[i]);
			pr("ang", ang, y[i], x[i]);
			ld opp = ang-pi;
			if(opp < -eps){
				opp += 2*pi;
			}
			auto it = angs.lower_bound(opp-eps);
			if(it != angs.end() and abs(*it-opp) < eps)
				cnt++;
			
			if(size(angs)){
				it = angs.lower_bound(ang-eps);
				auto pre = it, nx = it;
				if(pre == angs.begin())
					pre = --angs.end();
				else pre--;
				if(nx == angs.end())
					nx = angs.begin();
				
				if(pre != angs.end()){
					//do nothing for the first time
					if(size(angs) > 1)
						up(*pre, *nx, 0);
					up(*pre, ang, 1);
					up(ang, *nx, 1);
				}
			}
			angs.insert(ang);
		}
		else{
			scan(i);
			pr("del", i);

			pts.erase(pts.lower_bound({x[i], y[i]})); // eps?
			ld ang = atan2(y[i], x[i]);
			pr("ang", ang, y[i], x[i]);
			ld opp = ang-pi;
			if(opp < -eps)
				opp += 2*pi;
			
			auto it = angs.lower_bound(opp-eps);
			if(it != angs.end() and abs(*it-opp) < eps)
				cnt--;
			
			if(size(angs)){
				it = angs.lower_bound(ang-eps);
				auto pre = it, nx = it;
				if(pre == angs.begin())
					pre = --angs.end();
				else pre--;
				if(nx == angs.end())
					nx = angs.begin();
				
				if(pre != angs.end()){
					//do nothing for the first time
					if(size(angs) > 1)
						up(*pre, *nx, 1);
					up(*pre, ang, 0);
					up(ang, *nx, 0);
				}
			}
			angs.erase(angs.lower_bound(ang-eps)); //eps
		}
		
		auto it = pts.lower_bound({0, 0});
		pr("f", it->first, it->second);
		pr("cnt", cnt);
		if(it != pts.end() and abs(it->first) < eps and abs(it->second) < eps){
			print(1);
			continue;
		}
		if(cnt){
			print(2);
			continue;
		}
		if(size(difs)){
			auto itr = --difs.end();
			if(itr != difs.end() and *itr < pi){
				print(3);
				continue;
			}
		}
		print(0);
	}
}

Compilation message

Mixture.cpp: In function 'void up(ld, ld, bool)':
Mixture.cpp:38:5: warning: left operand of comma operator has no effect [-Wunused-value]
   38 |  pr("dif", dif, b);
      |     ^~~~~
Mixture.cpp:38:17: warning: right operand of comma operator has no effect [-Wunused-value]
   38 |  pr("dif", dif, b);
      |                 ^
Mixture.cpp: In function 'int main()':
Mixture.cpp:55:5: warning: left operand of comma operator has no effect [-Wunused-value]
   55 |  pr("pi", pi);
      |     ^~~~
Mixture.cpp:56:5: warning: left operand of comma operator has no effect [-Wunused-value]
   56 |  pr("init", a, b, c, x[0], y[0]);
      |     ^~~~~~
Mixture.cpp:56:16: warning: right operand of comma operator has no effect [-Wunused-value]
   56 |  pr("init", a, b, c, x[0], y[0]);
      |                ^
Mixture.cpp:56:19: warning: right operand of comma operator has no effect [-Wunused-value]
   56 |  pr("init", a, b, c, x[0], y[0]);
      |                   ^
Mixture.cpp:56:25: warning: right operand of comma operator has no effect [-Wunused-value]
   56 |  pr("init", a, b, c, x[0], y[0]);
      |                         ^
Mixture.cpp:56:25: warning: right operand of comma operator has no effect [-Wunused-value]
   56 |  pr("init", a, b, c, x[0], y[0]);
      |                      ~~~^
Mixture.cpp:64:7: warning: left operand of comma operator has no effect [-Wunused-value]
   64 |    pr("ins", a, b, c, x[i], y[i]);
      |       ^~~~~
Mixture.cpp:64:17: warning: right operand of comma operator has no effect [-Wunused-value]
   64 |    pr("ins", a, b, c, x[i], y[i]);
      |                 ^
Mixture.cpp:64:20: warning: right operand of comma operator has no effect [-Wunused-value]
   64 |    pr("ins", a, b, c, x[i], y[i]);
      |                    ^
Mixture.cpp:64:26: warning: right operand of comma operator has no effect [-Wunused-value]
   64 |    pr("ins", a, b, c, x[i], y[i]);
      |                          ^
Mixture.cpp:64:26: warning: right operand of comma operator has no effect [-Wunused-value]
   64 |    pr("ins", a, b, c, x[i], y[i]);
      |                       ~~~^
Mixture.cpp:67:7: warning: left operand of comma operator has no effect [-Wunused-value]
   67 |    pr("ang", ang, y[i], x[i]);
      |       ^~~~~
Mixture.cpp:67:22: warning: right operand of comma operator has no effect [-Wunused-value]
   67 |    pr("ang", ang, y[i], x[i]);
      |                      ^
Mixture.cpp:67:22: warning: right operand of comma operator has no effect [-Wunused-value]
   67 |    pr("ang", ang, y[i], x[i]);
      |                   ~~~^
Mixture.cpp:97:7: warning: left operand of comma operator has no effect [-Wunused-value]
   97 |    pr("del", i);
      |       ^~~~~
Mixture.cpp:101:7: warning: left operand of comma operator has no effect [-Wunused-value]
  101 |    pr("ang", ang, y[i], x[i]);
      |       ^~~~~
Mixture.cpp:101:22: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |    pr("ang", ang, y[i], x[i]);
      |                      ^
Mixture.cpp:101:22: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |    pr("ang", ang, y[i], x[i]);
      |                   ~~~^
Mixture.cpp:131:6: warning: left operand of comma operator has no effect [-Wunused-value]
  131 |   pr("f", it->first, it->second);
      |      ^~~
Mixture.cpp:132:6: warning: left operand of comma operator has no effect [-Wunused-value]
  132 |   pr("cnt", cnt);
      |      ^~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Execution timed out 2073 ms 256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Execution timed out 2073 ms 256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Execution timed out 2073 ms 256 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Execution timed out 2073 ms 256 KB Time limit exceeded
4 Halted 0 ms 0 KB -