Submission #997682

#	Time	Username	Problem	Language	Result	Execution time	Memory
997682		lucascgar	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	604 KiB

triusis

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
INVERTER PROBLEMA É ÚTIL:
LEAST AMOUNT TO MAKE FIXED:
LARGEST SUBSEQUENCE OF FIXED PILLARS

last fixed i

h[i] + (j-i-1)*M

turn h[i] into reduction to i (have to use double but it works):
i = i - h[i]/m
*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 2e5+10;

int h[MAXN];

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;

    vector<double> lis;  // increasing subsequence of positions: lis[i] = last j position of subsequence of size i

    for (int i=1;i<=n;i++){  // try to add you to some sequence if you are fixed
        cin >> h[i];
        if (h[i] > m*i) continue;  // all values must be reachable

        double tg = i - h[i]/m;  // obligatory >=0

        if (lis.empty()){
            lis.push_back(tg);
        }else{

            int p = upper_bound(lis.begin(), lis.end(), tg) - lis.begin();

            if (p == lis.size()) lis.push_back(tg);
            else lis[p] = tg;

        }

    }

    cout << n-lis.size() << "\n";

    return 0;
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             if (p == lis.size()) lis.push_back(tg);
      |                 ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37