제출 #1284168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284168		janson0109	3개의 봉우리 (IOI25_triples)	C++20	70 / 100	126 ms	18848 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;

long long count_triples(std::vector<int> H) {
    int N = H.size();
    ll ans = 0;
    for(int i=0; i<N; i++) {
        int j = H[i] + i;
        if(i < j && j < N) {
            int k1 = H[j] + i, k2 = H[j] + j, k3 = j - H[j];
            if(i < k1 && k1 < N && H[k1] == abs(k1 - j)) ans++;
            if(j < k2 && k2 < N && H[k2] == k2 - i) ans++;
            if(i < k3 && k3 < j && H[k3] == k3 - i) ans++;
        }
    }
    for(int j=0; j<N; j++) {
        int i = j - H[j];
        if(0 <= i && i < j) {
            int k = H[i] + j;
            if(j < k && k < N && H[k] == k - i) ans++;
        }
    }
    map<int,vector<int>> mp;
    for(int i=0; i<N; i++) mp[H[i]-i].push_back(i);
    int d = sqrt(N);
    for(auto & p : mp) {
        if(p.S.size() <= d) {
            for(int x=0; x<p.S.size(); x++) for(int y=x+1; y<p.S.size(); y++) {
                int i=p.S[x], j = p.S[y], k = H[i] + j;
                if(j < k && k < N && H[k] == j-i) ans++;
            }
        } else {
            for(int k=0; k<N; k++) {
                int sm = k - p.F, df = H[k];
                if((sm - df) % 2 == 0) {
                    int i = (sm-df)/2, j = (sm+df)/2;
                    if(0 <= i && i < j && j < k && H[i]-i == p.F && H[j]-j == p.F) ans++;
                }
            }
        }
    }
    for(int i=0; i<N; i++) {
        int d1 = H[i], d2 = H[i]/2;
        if(i + 2*d1 < N && ((H[i+d1] == d1 && H[i+2*d1] == 2*d1) || (H[i+d1] == 2*d1 && H[i+2*d1] == d1))) ans--;
        if(H[i] % 2 == 0 && i + 2*d2 < N && H[i+d2] == d2 && H[i+2*d2] == d2) ans--;
    }
    return ans;
}

std::vector<int> construct_range(int M, int K) {
    return {1, 1, 1};
}

• 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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5