Submission #1249456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249456		jtnydv25	3개의 봉우리 (IOI25_triples)	C++20	100 / 100	98 ms	31300 KiB

triples

#include "triples.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl "\n" // remove in interactive
#endif

// mt19937_64 for 64 bit
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int x, int y){
	return uniform_int_distribution<int>(x, y)(rng);
}


long long count_triples(vector<int> H){
    int n = H.size();
    const int OFFSET = n;
    vector<vector<int>> at_sum(2 * n + 1), at_diff(2 * n + 1);
    for(int i = 0; i < n; i++){
        at_sum[i + H[i]].push_back(i);
        at_diff[i - H[i] + OFFSET].push_back(i);
    }
    int ans = 0;
    // right-most is highest
    for(int k = 0; k < n; k++){
        int i = k - H[k];
        if(i < 0 || H[i] >= H[k]) continue;
        {
            int j = k  - H[i];
            if(H[j] == j - i) ans++;
        }

        {
            int j = i + H[i];
            if(H[j] == k - j && k + i != 2 * j) ans++;
        }
    }
    // left-most is highest
    for(int i = 0; i < n; i++){
        int k = i + H[i];
        if(k >= n || H[k] >= H[i]) continue;
        {
            int j = k - H[k];
            if(H[j] == j - i) ans++;
        }

        {
            int j = i + H[k];
            if(H[j] == k - j && k + i != 2 * j) ans++;
        }
    }
    // middle is highest
    for(int j = 0; j < n; j++){
        for(int i: at_sum[j]){
            if(H[i] >= H[j] || i >= j) continue;
            int Hk = H[j] - H[i];
            int k = j + Hk;
            if(k < n && H[k] == Hk && H[i] != Hk) {
                ans++;
            }
        }

        if(sz(at_sum[j + H[j]]) < sz(at_diff[j - H[j] + OFFSET])){
            for(int k: at_sum[j + H[j]]){
                if(H[k] >= H[j] || k <= j) continue;
                int i = j - H[k];
                if(i < 0) continue;
                if(H[i] + H[k] == H[j]) ans++;
            }
        } else{
            for(int i: at_diff[j - H[j] + OFFSET]){
                if(H[i] >= H[j] || i >= j) continue;
                int k = j + H[i];
                if(k >= n) continue;
                if(H[k] + H[i] == H[j]) ans++;
            }
        }
    }
    return ans;
}

std::vector<int> construct_range(int n, int req) {
    if(n == 20) return {2, 1, 1, 3, 2, 3, 4, 1, 2, 1, 3, 1, 3, 2, 3, 4, 1, 2, 1, 3};
    if(n == 500) return {2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,18,17,16,15,14,13,12,11,10,9,22,21,20,19,18,17,16,41,40,39,38,37,36,35,34,7,32,31,30,29,42,41,40,39,38,37,36,43,20,41,40,43,42,63,62,13,60,71,70,31,68,67,20,65,64,63,24,61,60,59,70,69,68,67,66,7,18,43,50,11,90,89,88,87,56,43,4,83,82,81,80,49,104,103,102,101,100,99,30,71,96,95,94,93,36,23,64,105,104,19,102,29,84,113,112,25,110,23,2,51,92,93,132,131,130,129,44,85,86,125,40,123,64,125,6,127,20,129,18,57,72,73,84,53,4,87,138,65,66,21,108,61,62,155,154,15,152,151,150,149,170,93,34,95,166,165,164,163,28,161,42,43,82,187,84,133,36,37,182,151,180,179,178,13,176,175,144,185,120,183,182,21,22,65,166,113,192,57,190,59,172,159,192,175,8,9,124,165,180,201,120,183,42,1,44,173,60,55,90,191,152,139,234,155,84,29,184,31,160,101,148,141,224,21,20,23,22,229,156,69,230,235,152,233,116,245,164,219,242,207,80,259,56,125,212,255,2,253,130,119,48,47,194,67,124,95,224,127,262,141,260,59,58,183,104,135,194,269,82,109,190,27,112,25,88,285,74,73,260,221,120,223,38,79,36,83,82,169,158,171,88,87,174,91,90,165,224,53,168,51,220,99,98,59,224,57,62,323,60,11,150,67,318,65,70,185,68,187,318,189,160,135,78,137,26,121,140,209,198,127,32,129,128,35,132,15,264,19,40,221,180,21,138,157,24,101,84,99,188,29,106,149,32,151,106,111,6,109,278,9,40,159,118,21,14,3,162,17,24,167,8,167,74,5,126,25,8,79,130,81,220,3,84,63,16,141,142,139,68,11,70,147,8,73,190,235,4,131,48,101,80,103,158,53,42,55,140,39,58,47,90,49,34,115,46,31,168,39,120,41,36,59,38,23,56,41,4,77,28,51,30,69,48,33,66,73,68,193,70,61,40,63,58,65,60,83,62,79,80,71,50,5,52,7,54,71,10,79,2,83,60,5,66,3,64,81,82,117,12,69,10,71,88,7};
    while(true){ // keep running
        for(int t = sqrt(n); t * t <= 10 * n; t = max(t + 1,(int)(t * 1.11))){
            vector<int> H(n, -1);
            vector<bool> used(n + 1, false);
            for(int qq = 0; qq < 5; qq++){
                set<int> vals;
                // return 0;
                for(int i = 2; i <= t; i+=2) vals.insert(i);
                while(sz(vals) < 2 * t){
                    int upper = n == 20 ? n/2: 2 * n / 3;
                    vals.insert(getRand(1, upper) * 2);
                }
                vector<int> V(all(vals));
                for(int diff: V){
                    for(int sum: V){
                        if((sum + diff) % 2 == 1) continue;
                        int i = (sum + diff) / 2;
                        int h = (sum - diff) / 2;
                        if(h >= n || h < 1) continue;
                        if(i < 0 || i >= n) continue;
                        if(used[i]) continue;
                        if(h > 0 && h < n){
                            H[i] = h;
                            // used[i] = true;
                        }
                    }
                }
                for(int i = 0; i < n; i++){
                    if(H[i] != -1){
                        used[i] = true;
                    }
                }
            }
            int filled = n;
            for(int i = 0; i < n; i++){
                if(H[i] == -1){
                    H[i] = getRand(1, 2);
                    filled--;
                }
            }
            int got = count_triples(H);
            if(got >= req){
                return H;
            }
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5