Submission #692477

#	Time	Username	Problem	Language	Result	Execution time	Memory
692477		sharaelong	The Big Prize (IOI17_prize)	C++17	100 / 100	51 ms	1888 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 2e5 + 1;

int trash = 0;
pii res[MAX_N];

void secure_ask(int x) {
    if (res[x].first == -1) {
        vector<int> tmp = ask(x);
        res[x] = { tmp[0], tmp[1] };
    }
}

void solve(int l, int r) {
    while (l <= r) {
        secure_ask(l);
        if (res[l].first + res[l].second == trash) break;
        l++;
    }
    while (l <= r) {
        secure_ask(r);
        if (res[r].first + res[r].second == trash) break;
        r--;
    }
    if (l >= r) return;

    int m = (l+r) / 2;
    while (m < r) {
        secure_ask(m);
        if (res[m].first + res[m].second == trash) {
            if (res[l].first < res[m].first) solve(l, m);
            if (res[m].first < res[r].first) solve(m, r);
            return;
        }
        m++;
    }
    m = (l+r) / 2;
    while (m > l) {
        secure_ask(m);
        if (res[m].first + res[m].second == trash) {
            if (res[l].first < res[m].first) solve(l, m);
            if (res[m].first < res[r].first) solve(m, r);
            return;
        }
        m--;
    }
}

int find_best(int n) {
    memset(res, -1, sizeof res);
    
    int rtn = sqrt(n);
    for (int i=rtn; i<n; i+=rtn) {
        vector<int> tmp = ask(i);
        if (tmp[0] + tmp[1] == 0) return i;
        trash = max(trash, tmp[0]+tmp[1]); 
        res[i] = { tmp[0], tmp[1] };
    }
    for (int i=rtn; i<n; i+=rtn) solve(i-rtn, i);
    solve(n-1-rtn, n-1);

    for (int i=0; i<n; ++i) {
        if (res[i].first + res[i].second == 0) {
            return i;
        }
    }
    assert(false);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:55:31: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'pii' {aka 'struct std::pair<int, int>'} with no trivial copy-assignment [-Wclass-memaccess]
   55 |     memset(res, -1, sizeof res);
      |                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from prize.h:1,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'pii' {aka 'struct std::pair<int, int>'} declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80