oj.uz

Submission #297397

# Submission time Handle Problem Language Result Execution time Memory
297397 2020-09-11T14:28:48 Z crackersamdjam Mixture (BOI20_mixture) C++17
0 / 100
 1 ms 384 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...);}

// #define ONLINE_JUDGE
//#define LOCAL
#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 = long double;
const int MM = 1e5+5;
const ld pi = acos(-1), eps = 1e-13;

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

Compilation message

Mixture.cpp: In function 'void up(ld, ld, bool)':
Mixture.cpp:40:5: warning: left operand of comma operator has no effect [-Wunused-value]
   40 |  pr("dif", dif, b);
      |     ^~~~~
Mixture.cpp:40:17: warning: right operand of comma operator has no effect [-Wunused-value]
   40 |  pr("dif", dif, b);
      |                 ^
Mixture.cpp: In function 'int main()':
Mixture.cpp:59:5: warning: left operand of comma operator has no effect [-Wunused-value]
   59 |  pr("pi", pi);
      |     ^~~~
Mixture.cpp:60:5: warning: left operand of comma operator has no effect [-Wunused-value]
   60 |  pr("init", a, b, c, x[0], y[0]);
      |     ^~~~~~
Mixture.cpp:60:16: warning: right operand of comma operator has no effect [-Wunused-value]
   60 |  pr("init", a, b, c, x[0], y[0]);
      |                ^
Mixture.cpp:60:19: warning: right operand of comma operator has no effect [-Wunused-value]
   60 |  pr("init", a, b, c, x[0], y[0]);
      |                   ^
Mixture.cpp:60:25: warning: right operand of comma operator has no effect [-Wunused-value]
   60 |  pr("init", a, b, c, x[0], y[0]);
      |                         ^
Mixture.cpp:60:25: warning: right operand of comma operator has no effect [-Wunused-value]
   60 |  pr("init", a, b, c, x[0], y[0]);
      |                      ~~~^
Mixture.cpp:63:6: warning: left operand of comma operator has no effect [-Wunused-value]
   63 |   pr(t, "---------");
      |      ^
Mixture.cpp:69:7: warning: left operand of comma operator has no effect [-Wunused-value]
   69 |    pr("ins", a, b, c, x[i], y[i]);
      |       ^~~~~
Mixture.cpp:69:17: warning: right operand of comma operator has no effect [-Wunused-value]
   69 |    pr("ins", a, b, c, x[i], y[i]);
      |                 ^
Mixture.cpp:69:20: warning: right operand of comma operator has no effect [-Wunused-value]
   69 |    pr("ins", a, b, c, x[i], y[i]);
      |                    ^
Mixture.cpp:69:26: warning: right operand of comma operator has no effect [-Wunused-value]
   69 |    pr("ins", a, b, c, x[i], y[i]);
      |                          ^
Mixture.cpp:69:26: warning: right operand of comma operator has no effect [-Wunused-value]
   69 |    pr("ins", a, b, c, x[i], y[i]);
      |                       ~~~^
Mixture.cpp:74:7: warning: left operand of comma operator has no effect [-Wunused-value]
   74 |    pr("ang", ang, y[i], x[i]);
      |       ^~~~~
Mixture.cpp:74:22: warning: right operand of comma operator has no effect [-Wunused-value]
   74 |    pr("ang", ang, y[i], x[i]);
      |                      ^
Mixture.cpp:74:22: warning: right operand of comma operator has no effect [-Wunused-value]
   74 |    pr("ang", ang, y[i], x[i]);
      |                   ~~~^
Mixture.cpp:81:8: warning: left operand of comma operator has no effect [-Wunused-value]
   81 |     pr("HELP", *it, ang, opp, abs(*it-opp));
      |        ^~~~~~
Mixture.cpp:81:26: warning: right operand of comma operator has no effect [-Wunused-value]
   81 |     pr("HELP", *it, ang, opp, abs(*it-opp));
      |                          ^~~
Mixture.cpp:81:42: warning: right operand of comma operator has no effect [-Wunused-value]
   81 |     pr("HELP", *it, ang, opp, abs(*it-opp));
      |                                          ^
Mixture.cpp:107:7: warning: left operand of comma operator has no effect [-Wunused-value]
  107 |    pr("del", i);
      |       ^~~~~
Mixture.cpp:113:7: warning: left operand of comma operator has no effect [-Wunused-value]
  113 |    pr("ang", ang, y[i], x[i]);
      |       ^~~~~
Mixture.cpp:113:22: warning: right operand of comma operator has no effect [-Wunused-value]
  113 |    pr("ang", ang, y[i], x[i]);
      |                      ^
Mixture.cpp:113:22: warning: right operand of comma operator has no effect [-Wunused-value]
  113 |    pr("ang", ang, y[i], x[i]);
      |                   ~~~^
Mixture.cpp:144:6: warning: left operand of comma operator has no effect [-Wunused-value]
  144 |   pr("f", it->first, it->second);
      |      ^~~
Mixture.cpp:145:6: warning: left operand of comma operator has no effect [-Wunused-value]
  145 |   pr("cnt", cnt);
      |      ^~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -