Submission #1257008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257008		otarius	Triple Peaks (IOI25_triples)	C++20	75.29 / 100	118 ms	16196 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 2 * 1e5 + 15;
const int sq = 450;

vector<int> v[2 * maxN];

ll count_triples(vector<int> h) {
    ll ans = 0;
    int n = h.size();
    for (int i = 0; i < n; i++) {
        int k = i + h[i];
        if (k < 0 || k >= n) continue;
        int j = h[k] + i;
        if (j < 0 || j >= n) continue;
        ans += (h[i] == h[j] + h[k]);
    }

    for (int i = 0; i < n; i++) {
        int k = i + h[i];
        if (k < 0 || k >= n) continue;
        int j = k - h[k];
        if (j < 0 || j >= n) continue;
        ans += (h[i] == h[j] + h[k] && h[j] != h[k]);
    }

    for (int k = 0; k < n; k++) {
        int i = k - h[k];
        if (i < 0 || i >= n) continue;
        int j = h[i] + i;
        if (j < 0 || j >= n) continue;
        ans += (h[k] == h[i] + h[j]);
    }

    for (int k = 0; k < n; k++) {
        int i = k - h[k];
        if (i < 0 || i >= n) continue;
        int j = k - h[i];
        if (j < 0 || j >= n) continue;
        ans += (h[k] == h[i] + h[j] && h[i] != h[j]);
    }

    for (int i = 0; i < n; i++) {
        int j = i + h[i];
        if (j < 0 || j >= n) continue;
        int k = h[j] + i;
        if (k < 0 || k >= n) continue;
        ans += (h[j] == h[i] + h[k] && h[i] != h[k]);
    }

    // return ans;


    for (int i = 0; i < n; i++)
        v[h[i] - i + n].pb(i);
    for (int t = 0; t <= 2 * n; t++) {
        if (v[t].size() <= sq) {
            for (int i = 0; i < v[t].size(); i++) {
                for (int j = i + 1; j < v[t].size(); j++) {
                    int k = h[v[t][i]] + v[t][j];
                    if (k < 0 || k >= n) continue;
                    ans += (h[v[t][i]] == k - v[t][j] && h[v[t][j]] == k - v[t][i] && h[k] == v[t][j] - v[t][i]);
                }
            }
        } else {
            for (int k = 0; k < n; k++) {
                int x = t - n, y = k - x;

                if (h[k] % 2 == y % 2) {
                    int i = (y - h[k]) / 2;
                    int j = (y + h[k]) / 2;
                    ans += (0 <= i && i < n && 0 <= j && j < n && h[i] - i == x && h[j] - j == x);
                }
            }
        }
    }

    return ans;
}
vector<int> construct_range(int m, int k) {
  vector<int> ans(m);
  for (int i = 0; i < m; i++)
    ans[i] = (i % 3 ? 1 : 2);
  return ans;
}

// namespace {
// // BEGIN SECRET
// const std::string input_secret  = "jB7KRtelfNrzhva6IhSoGAcDptqeBHJr";
// const std::string output_secret = "qOpG8GoYprN2GHwBEAOkfIfpiiFWanMx";
// const std::string extra_secret  = "nxz3K1mLpvlEac8SbN9hu4cFQ2jnBxG9";
// // END SECRET

// void run_part1() {
//   int N;
//   assert(1 == scanf("%d", &N));
//   std::vector<int> H(N);
//   for (int i = 0; i < N; i++)
//     scanf("%d", &H[i]);
//   fclose(stdin);

//   long long T = count_triples(H);

//   // BEGIN SECRET
//   printf("%s\n", output_secret.c_str());
//   printf("OK\n");
//   // END SECRET
//   printf("%lld\n", T);
//   fclose(stdout);
// }

// void run_part2() {
//   int M, K;
//   assert(2 == scanf("%d %d", &M, &K));
//   fclose(stdin);

//   // BEGIN SECRET
//   printf("%s\n", output_secret.c_str());
//   // END SECRET
//   std::vector<int> H = construct_range(M, K);

//   // BEGIN SECRET
//   printf("%s\n", extra_secret.c_str());
//   // END SECRET
//   int N = H.size();
//   printf("%d\n", N);
//   for (int i = 0; i < N; i++)
//     printf("%d%c", H[i], " \n"[i + 1 == N]);
//   fclose(stdout);
// }

// } // namespace


// int main() {
//   // BEGIN SECRET
//   char secret[1000];
//   assert(1 == scanf("%999s", secret));
//   if (std::string(secret) != input_secret) {
//     printf("%s\n", output_secret.c_str());
//     printf("PV\n");
//     printf("Possible tampering with the input\n");
//     fclose(stdout);
//     return 0;
//   }
//   // END SECRET
//   int part;
//   assert(1 == scanf("%d", &part));
//   if (part == 1)
//     run_part1();
//   else if (part == 2)
//     run_part2();
//   // BEGIN SECRET
//   else {
//     printf("%s\n", output_secret.c_str());
//     printf("PV\n");
//     printf("Possible tampering with the input\n");
//     fclose(stdout);
//     return 0;
//   }
//   // END SECRET

//   return 0;
// }

• 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: 3 / 5
• Subtask 8: 1.245 / 5
• Subtask 9: 0.4998 / 5
• Subtask 10: 0.2143 / 5
• Subtask 11: 0.25 / 5
• Subtask 12: 0.0833 / 5