oj.uz

Submission #426231

# Submission time Handle Problem Language Result Execution time Memory
426231 2021-06-13T15:34:03 Z 79brue Aliens (IOI16_aliens) C++14
4 / 100
 7 ms 460 KB 
#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

typedef long long ll;

int n, m, k;
ll x[500002], y[500002];

void makeArr(vector<int>&, vector<int>&);
pair<ll, int> calc(ll);

ll take_photos(int N, int M, int K, vector<int> r, vector<int> c){
    m = M, k = K;
    makeArr(r, c);
    k = min(n, k);

    assert(calc(0).second == n);
    assert(calc(1e12*2+1).second == 1);

    ll L = 0, R = 1e12, ans = 1e12;
    for(int i=0; i<=10000; i++){
        if(calc(i).second <= k){
            ans = i;
            break;
        }
    }
//    while(L < R){
//        ll M = (L+R)>>1;
//        if(calc(M).second <= k) ans = M, R = M-1;
//        else L = M+1;
//    }

    ll ret = LLONG_MAX;
    for(ll lambda = max(ans, 0LL); lambda <= ans+1; lambda++){
        auto x = calc(lambda);
        if(x.second != k) continue;
        ret = min(ret, x.first - lambda*(x.second-1));
    }
    if(ret != LLONG_MAX) return ret;

    auto p1 = calc(ans);
    auto p2 = calc(ans-1);
    assert(p1.second <= k && p2.second > k);
    int x1 = p1.second, x2 = p2.second;
    ll y1 = p1.first, y2 = p2.first;
    return x1*10000+x2;
}

void makeArr(vector<int> &r, vector<int> &c){
    vector<pair<int, int> > vec;
    int N = (int)r.size();
    for(int i=0; i<N; i++){
        if(r[i] > c[i]) swap(r[i], c[i]);
        vec.push_back(make_pair(r[i], c[i]));
    }
    sort(vec.begin(), vec.end(), [&](pair<int, int> &x, pair<int, int> &y){
        return x.second < y.second;
    });

    vector<pair<int, int> > stk;
    for(int i=0; i<N; i++){
        if(!stk.empty() && stk.back().second == vec[i].second && stk.back().first <= vec[i].first) continue;
        while(!stk.empty() && stk.back().first >= vec[i].first) stk.pop_back();
        stk.push_back(vec[i]);
    }

    n = (int)stk.size();
    for(int i=1; i<=n; i++) x[i] = stk[i-1].first, y[i] = stk[i-1].second;
}

ll quot(ll a, ll b){
    if(a>=0) return a/b;
    return a/b - !!(a%b);
}

struct Line{
    ll a, b; ll start; int cnt;
    Line(ll a, ll b, int cnt): a(a), b(b), cnt(cnt){}
    Line(ll a, ll b, ll start, int cnt): a(a), b(b), start(start), cnt(cnt){}

    ll val(ll x){
        return a*x+b;
    }

    ll cross(const Line &r)const{
        ll A = r.a - a;
        ll B = r.b - b;
        assert(A >= 0);
        return quot(-B+A-1, A);
    }
};

ll DP[500002];
int cnt[500002];
vector<Line> vec;
int pnt = 0;

pair<ll, int> calc(ll lambda){
    for(int i=1; i<=n; i++){
        DP[i] = (y[i] - x[1] + 1) * (y[i] - x[1] + 1);
        cnt[i] = 1;
    }
    pnt = 0;
    vec.clear();
    vec.push_back(Line(2, 3e12, -1e18, 0));

    for(int i=1; i<=n; i++){
        while(pnt >= (int)vec.size() || vec[pnt].start > y[i]) --pnt;
        while(pnt+1 < (int)vec.size() && y[i] >= vec[pnt+1].start) ++pnt;

        ll val = vec[pnt].val(y[i]) + y[i]*y[i] + lambda;
        if(DP[i] > val){
            DP[i] = val;
            cnt[i] = vec[pnt].cnt + 1;
        }

        if(i==n) break;
        Line tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1) * y[i] * 2 - y[i] * y[i] + DP[i], cnt[i]);
        if(x[i+1] > y[i]) tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1)*(x[i+1]-1) + DP[i], cnt[i]);

        while((int)vec.size() >= 2 && vec.back().start > tmp.cross(vec[(int)vec.size()-1])){
            vec.pop_back();
            if((int)vec.size() == pnt) pnt--;
        }
        tmp.start = tmp.cross(vec.back());
        vec.push_back(tmp);
    }

    return make_pair(DP[n], cnt[n]);
}

Compilation message

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:22:8: warning: unused variable 'L' [-Wunused-variable]
   22 |     ll L = 0, R = 1e12, ans = 1e12;
      |        ^
aliens.cpp:22:15: warning: unused variable 'R' [-Wunused-variable]
   22 |     ll L = 0, R = 1e12, ans = 1e12;
      |               ^
aliens.cpp:47:8: warning: unused variable 'y1' [-Wunused-variable]
   47 |     ll y1 = p1.first, y2 = p2.first;
      |        ^~
aliens.cpp:47:23: warning: unused variable 'y2' [-Wunused-variable]
   47 |     ll y1 = p1.first, y2 = p2.first;
      |                       ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 1
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 1
4 Correct 1 ms 204 KB Correct answer: answer = 5
5 Correct 1 ms 204 KB Correct answer: answer = 41
6 Runtime error 7 ms 460 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Runtime error 7 ms 460 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Runtime error 7 ms 460 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Runtime error 7 ms 460 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Correct answer: answer = 4
2 Correct 1 ms 204 KB Correct answer: answer = 4
3 Correct 1 ms 204 KB Correct answer: answer = 4
4 Correct 1 ms 204 KB Correct answer: answer = 12
5 Correct 1 ms 204 KB Correct answer: answer = 52
6 Correct 1 ms 204 KB Correct answer: answer = 210
7 Correct 1 ms 204 KB Correct answer: answer = 88
8 Correct 1 ms 204 KB Correct answer: answer = 7696
9 Correct 1 ms 204 KB Correct answer: answer = 1
10 Correct 1 ms 204 KB Correct answer: answer = 2374
11 Correct 1 ms 204 KB Correct answer: answer = 9502
12 Correct 1 ms 204 KB Correct answer: answer = 49
13 Correct 1 ms 204 KB Correct answer: answer = 151
14 Correct 1 ms 204 KB Correct answer: answer = 7550
15 Correct 1 ms 332 KB Correct answer: answer = 7220
16 Correct 1 ms 204 KB Correct answer: answer = 7550
17 Correct 1 ms 204 KB Correct answer: answer = 10000
18 Correct 1 ms 204 KB Correct answer: answer = 10000
19 Correct 1 ms 204 KB Correct answer: answer = 624
20 Correct 1 ms 204 KB Correct answer: answer = 10000
21 Correct 1 ms 204 KB Correct answer: answer = 1
22 Correct 1 ms 204 KB Correct answer: answer = 4
23 Correct 1 ms 204 KB Correct answer: answer = 1
24 Correct 1 ms 204 KB Correct answer: answer = 5
25 Correct 1 ms 204 KB Correct answer: answer = 41
26 Runtime error 7 ms 460 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -