Submission #883918

#	Time	Username	Problem	Language	Result	Execution time	Memory
883918		macneil	Let's Win the Election (JOI22_ho_t3)	C++17	39 / 100	951 ms	600 KiB

Main

// очень классно когда уже на втором туре сидишь сдал на 100 а твое решение тупо ломают а когда у когото n^2logn на n до 1e6 заходит всем пофиг почемуто
// тут тоже кстати можно тл в два раза обрезать чтоб не расслаблялись и отжиг на еще меньше заходил ну это так идея вам для размышления

#pragma GCC optimize("O3") 
#pragma GCC optimize("unroll-loops") 
  
// #pragma GCC optimize("Ofast,unroll-loops") 
  
// #pragma GCC optimize(3) 
// #pragma GCC optimize("Ofast") 
// #pragma GCC optimize("inline") 
// #pragma GCC optimize("-fgcse") 
// #pragma GCC optimize("-fgcse-lm") 
// #pragma GCC optimize("-fipa-sra") 
// #pragma GCC optimize("-ftree-pre") 
// #pragma GCC optimize("-ftree-vrp") 
// #pragma GCC optimize("-fpeephole2") 
// #pragma GCC optimize("-ffast-math") 
// #pragma GCC optimize("-fsched-spec") 
// #pragma GCC optimize("-falign-jumps") 
// #pragma GCC optimize("-falign-loops") 
// #pragma GCC optimize("-falign-labels") 
// #pragma GCC optimize("-fdevirtualize") 
// #pragma GCC optimize("-fcaller-saves") 
// #pragma GCC optimize("-fcrossjumping") 
// #pragma GCC optimize("-fthread-jumps") 
// #pragma GCC optimize("-freorder-blocks") 
// #pragma GCC optimize("-fschedule-insns") 
// #pragma GCC optimize("inline-functions") 
// #pragma GCC optimize("-ftree-tail-merge") 
// #pragma GCC optimize("-fschedule-insns2") 
// #pragma GCC optimize("-fstrict-aliasing") 
// #pragma GCC optimize("-falign-functions") 
// #pragma GCC optimize("-fcse-follow-jumps") 
// #pragma GCC optimize("-fsched-interblock") 
// #pragma GCC optimize("-fpartial-inlining") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("-freorder-functions") 
// #pragma GCC optimize("-findirect-inlining") 
// #pragma GCC optimize("-fhoist-adjacent-loads") 
// #pragma GCC optimize("-frerun-cse-after-loop") 
// #pragma GCC optimize("inline-small-functions") 
// #pragma GCC optimize("-finline-small-functions") 
// #pragma GCC optimize("-ftree-switch-conversion") 
// #pragma GCC optimize("-foptimize-sibling-calls") 
// #pragma GCC optimize("-fexpensive-optimizations") 
// #pragma GCC optimize("inline-functions-called-once") 
// #pragma GCC optimize("-fdelete-null-pointer-checks") 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>
 
using namespace std;
 
// #define int long long
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define f(a) for(int i = 0; i<a; ++i)
 
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef string str;
typedef vector<str> vestr;
typedef vector<int> vei;
typedef vector<vector<int>> veve;
 
mt19937 rnd(1329);
 
const int NUM = 685000;
 
int k;

int gen(int n){
    return min(rnd() % n, rnd() % n);
}
 
bool flip(int a, int b) {
    return ((rnd() % (a + b))) < a;
}
 
ld cost(vector<int> &a, vector<int> &b, vector<int> &inb, vector<int> &ord1, vector<int> &ord2) {
    int n = a.size();
    ld ans = 0;
    vector<int> auu;
    int ttt = 1;
    for (auto i : ord2) {
        if (inb[i]) {
            ans += (ld)(b[i]) / (ttt);
            ttt++;
        }
    }
    int ctt = ttt - 1;
    for (auto i : ord1) {
        if (ctt == k) break;
        if (!inb[i]) {
            ans += (ld)a[i] / (ttt);
            ctt++;
        }
    }
    return ans;
}
 
 
void solve() {
    int n;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    // for (int i = 0; i < n; ++i) if (b[i] == -1) b[i] = 1e14;
    vector<int> ord1(n), ord2(n);
    iota(all(ord1), 0);
    iota(all(ord2), 0);
    sort(all(ord1), [&](int i, int j){
        return a[i] < a[j];
    });
    sort(all(ord2), [&](int i, int j){
        if (b[i] == b[j]) return a[i] > a[j];
        return b[i] < b[j];
    });
    vector<int> notminusone;
    for (int i = 0; i < n; ++i) if (b[i] != -1) notminusone.push_back(i);
    sort(all(notminusone), [&](int i, int j){
        return b[i] < b[j];
    });
    ld ans = 0;
    for (int i = 0; i < k; ++i) ans += a[ord1[i]];
    if (notminusone.size() == 0) {
        cout << ans;
        return;
    }
    vector<int> inb(n);
    for (int i = 0; i < n; ++i) {
        if (b[i] == -1) continue;
        if (rnd() % 2 == 1) inb[i] = 1;
    }
    // inb[notminusone[notminusone.size() - 1]] = 1;
    if (ans > cost(a, b, inb, ord1, ord2)) {
        ans = cost(a, b, inb, ord1, ord2);
    }
    else {
        inb.clear();
        inb.resize(n);
    }
    ld prevans = ans;
    for (int i = 0; ; ++i) {
        vector<int> tt;
        for (int j = 0; j < rnd() % 5 + 1; ++j) {
            tt.push_back(gen(notminusone.size()));
            inb[notminusone[tt[j]]] ^= 1;
        }
        if (cost(a, b, inb, ord1, ord2) < prevans) {
            prevans = cost(a, b, inb, ord1, ord2);
            ans = min(ans, prevans);
        }
        else {
            for (auto e : tt) inb[notminusone[e]] ^= 1;
        }
        if (i % 1000 == 0) {
            if (clock() * 1.0 / CLOCKS_PER_SEC >= 0.95) break;
        }
    }
    cout << ans << '\n';
}
 
signed main() {
    int tc = 1;
    cout << fixed << setprecision(15);
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    cin >> tc;
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // cin >> tc;
#endif
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'bool flip(int, int)':
Main.cpp:96:32: warning: comparison of integer expressions of different signedness: 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |     return ((rnd() % (a + b))) < a;
      |            ~~~~~~~~~~~~~~~~~~~~^~~
Main.cpp: In function 'ld cost(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
Main.cpp:100:9: warning: unused variable 'n' [-Wunused-variable]
  100 |     int n = a.size();
      |         ^
Main.cpp: In function 'void solve()':
Main.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for (int j = 0; j < rnd() % 5 + 1; ++j) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23