Submission #217028

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217028	2020-03-28T18:09:42 Z	Blagojce	Akvizna (COCI19_akvizna)	C++11	Compilation error	0 ms	0 KB

akvizna

include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;
struct line{
        int K;
        ld m, b;
        bool isq;
        ld x;
        ld eval(ld X) const{
                return X * m + b;
        }
        ld intersect(const line &l) const{
                return 1.0 * (l.b - b) / (m - l.m);
        }
        bool operator < (const line &l) const{
                if(l.isq) return x < l.x;
                else return m > l.m;
        }
};
set<line> hull;
typedef set<line>::iterator iter;
bool cPrev(iter it){
        return it != hull.begin();
}
bool cNext(iter it){
        return it != hull.end() && next(it) != hull.end();
}
bool bad(const line &l1, const line &l2, const line &l3){
        return l1.intersect(l3) <= l1.intersect(l2);
}
bool bad(iter it){
        return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}
 
iter update(iter it){
        if(!cPrev(it)) return it;
        ld x = prev(it)->intersect(*it);
        line l = *it;
        l.x = x;
        it = hull.erase(it);
        return hull.insert(it, l);
 
}
void addLine(ld m, ld b, int K){
        line l;
        l.K = K;
        l.m = m, l.b = b, l.isq = false;
        l.x = -inf;
        iter it = hull.lower_bound(l);
 
        it = hull.insert(it, l);
        if(bad(it)){
                hull.erase(it);
                return;
        }
        while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
        while(cNext(it) && bad(next(it))) hull.erase(next(it));
        it = update(it);
        if(cPrev(it)) update(prev(it));
        if(cNext(it)) update(next(it));
}
pair<int,ld> query(ld x){
        line q;
        q.x = x;
        q.isq = true;
        iter it = --hull.lower_bound(q);
        int K = it->K;
        ld ret = it->eval(x);
 
        it ++;
        if(it != hull.end()){
                ld ret2 = it->eval(x);
                if(abs(ret - ret2) < eps){
                        K = min(K, it->K);
                }
        }
        return {K, ret};
}
 
ld ANS;
int calculate(ld lambda, int N){
        hull.clear();
        addLine(0, 0, 0);
        fr(i, 1, N){
                pair<int, ld> best = query(-1.0/i);
                ld currans = -best.nd + 1 - lambda;
                addLine(-i, -currans, best.st + 1);
        }
        pair<int, ld> best = query(-1.0/N);
        ANS = -best.nd + 1 - lambda;
        return best.st + 1;
}
ld solve(int N, int K){
        ld l = 0, r = 1;
        ld best = 0;
        fr(j, 0, 100){
                ld mid = (l + r) / 2;
                int i = calculate(mid, N);
                if(i <= K){
                        best = mid;
                        r = mid-eps;
                }
                else{
                        l = mid + eps;
                }
        }
        calculate(best, N);
        return ANS + K*best;
}
int main()
{
        int N, K;
        cin >> N >> K;
        cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
        return 0;
}

Compilation message

akvizna.cpp:1:1: error: 'include' does not name a type; did you mean '__has_include'?
 include <bits/stdc++.h>
 ^~~~~~~
 __has_include
akvizna.cpp:12:9: error: 'pair' does not name a type
 typedef pair<int,int> pii;
         ^~~~
akvizna.cpp:32:1: error: 'set' does not name a type; did you mean 'st'?
 set<line> hull;
 ^~~
 st
akvizna.cpp:33:9: error: 'set' does not name a type; did you mean 'st'?
 typedef set<line>::iterator iter;
         ^~~
         st
akvizna.cpp:34:12: error: 'iter' was not declared in this scope
 bool cPrev(iter it){
            ^~~~
akvizna.cpp:37:12: error: 'iter' was not declared in this scope
 bool cNext(iter it){
            ^~~~
akvizna.cpp:43:10: error: 'bool bad' redeclared as different kind of symbol
 bool bad(iter it){
          ^~~~
akvizna.cpp:40:6: note: previous declaration 'bool bad(const line&, const line&, const line&)'
 bool bad(const line &l1, const line &l2, const line &l3){
      ^~~
akvizna.cpp:43:10: error: 'iter' was not declared in this scope
 bool bad(iter it){
          ^~~~
akvizna.cpp:47:1: error: 'iter' does not name a type
 iter update(iter it){
 ^~~~
akvizna.cpp: In function 'void addLine(ld, ld, int)':
akvizna.cpp:61:9: error: 'iter' was not declared in this scope
         iter it = hull.lower_bound(l);
         ^~~~
akvizna.cpp:63:9: error: 'it' was not declared in this scope
         it = hull.insert(it, l);
         ^~
akvizna.cpp:63:9: note: suggested alternative: 'st'
         it = hull.insert(it, l);
         ^~
         st
akvizna.cpp:63:14: error: 'hull' was not declared in this scope
         it = hull.insert(it, l);
              ^~~~
akvizna.cpp:63:14: note: suggested alternative: 'll'
         it = hull.insert(it, l);
              ^~~~
              ll
akvizna.cpp:68:23: error: 'cPrev' cannot be used as a function
         while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
                       ^
akvizna.cpp:68:32: error: 'prev' was not declared in this scope
         while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
                                ^~~~
akvizna.cpp:68:32: note: suggested alternative: 'cPrev'
         while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
                                ^~~~
                                cPrev
akvizna.cpp:69:23: error: 'cNext' cannot be used as a function
         while(cNext(it) && bad(next(it))) hull.erase(next(it));
                       ^
akvizna.cpp:69:32: error: 'next' was not declared in this scope
         while(cNext(it) && bad(next(it))) hull.erase(next(it));
                                ^~~~
akvizna.cpp:69:32: note: suggested alternative: 'cNext'
         while(cNext(it) && bad(next(it))) hull.erase(next(it));
                                ^~~~
                                cNext
akvizna.cpp:70:14: error: 'update' was not declared in this scope
         it = update(it);
              ^~~~~~
akvizna.cpp:71:20: error: 'cPrev' cannot be used as a function
         if(cPrev(it)) update(prev(it));
                    ^
akvizna.cpp:71:30: error: 'prev' was not declared in this scope
         if(cPrev(it)) update(prev(it));
                              ^~~~
akvizna.cpp:71:30: note: suggested alternative: 'cPrev'
         if(cPrev(it)) update(prev(it));
                              ^~~~
                              cPrev
akvizna.cpp:72:20: error: 'cNext' cannot be used as a function
         if(cNext(it)) update(next(it));
                    ^
akvizna.cpp:72:30: error: 'next' was not declared in this scope
         if(cNext(it)) update(next(it));
                              ^~~~
akvizna.cpp:72:30: note: suggested alternative: 'cNext'
         if(cNext(it)) update(next(it));
                              ^~~~
                              cNext
akvizna.cpp: At global scope:
akvizna.cpp:74:1: error: 'pair' does not name a type
 pair<int,ld> query(ld x){
 ^~~~
akvizna.cpp: In function 'int calculate(ld, int)':
akvizna.cpp:94:9: error: 'hull' was not declared in this scope
         hull.clear();
         ^~~~
akvizna.cpp:94:9: note: suggested alternative: 'll'
         hull.clear();
         ^~~~
         ll
akvizna.cpp:97:17: error: 'pair' was not declared in this scope
                 pair<int, ld> best = query(-1.0/i);
                 ^~~~
akvizna.cpp:97:22: error: expected primary-expression before 'int'
                 pair<int, ld> best = query(-1.0/i);
                      ^~~
akvizna.cpp:98:31: error: 'best' was not declared in this scope
                 ld currans = -best.nd + 1 - lambda;
                               ^~~~
akvizna.cpp:98:31: note: suggested alternative: 'st'
                 ld currans = -best.nd + 1 - lambda;
                               ^~~~
                               st
akvizna.cpp:101:9: error: 'pair' was not declared in this scope
         pair<int, ld> best = query(-1.0/N);
         ^~~~
akvizna.cpp:101:14: error: expected primary-expression before 'int'
         pair<int, ld> best = query(-1.0/N);
              ^~~
akvizna.cpp:102:16: error: 'best' was not declared in this scope
         ANS = -best.nd + 1 - lambda;
                ^~~~
akvizna.cpp:102:16: note: suggested alternative: 'st'
         ANS = -best.nd + 1 - lambda;
                ^~~~
                st
akvizna.cpp: In function 'int main()':
akvizna.cpp:125:9: error: 'cin' was not declared in this scope
         cin >> N >> K;
         ^~~
akvizna.cpp:125:9: note: suggested alternative: 'main'
         cin >> N >> K;
         ^~~
         main
akvizna.cpp:126:9: error: 'cout' was not declared in this scope
         cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
         ^~~~
akvizna.cpp:126:17: error: 'fixed' was not declared in this scope
         cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
                 ^~~~~
akvizna.cpp:126:24: error: 'setprecision' was not declared in this scope
         cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
                        ^~~~~~~~~~~~
akvizna.cpp:126:55: error: 'endl' was not declared in this scope
         cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
                                                       ^~~~
akvizna.cpp:126:55: note: suggested alternative: 'nd'
         cout << fixed<<setprecision(9) <<solve(N, K)<<endl;
                                                       ^~~~
                                                       nd