제출 #1352245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1352245		d4n13l	3개의 봉우리 (IOI25_triples)	C++20	18 / 100	2096 ms	12824 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using ll = long long;

using namespace std;

long long count_triples(std::vector<int> h) {
    int n = h.size();
    vector <pair <int, int> > a;
    set <pair <int, int> > s;
    for (int i = 0; i < n; i++) {
        a.push_back({h[i],i});
        s.insert({h[i], i});
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (j>=n) {
                break;
            }
            bool one = false, two = false;
            if (h[i]==j-i) {
                if (s.count({h[j]+i-j, h[j]+i})) {
                    ans++;
                    one = true;
                }
                if (s.count({h[j]+j-i, h[j]+j})) {
                    ans++;
                }
            }
            if (h[j]==j-i and h[i]!=h[j]) {
                if (s.count({h[i]+i-j, h[i]+i})) {
                    ans++;
                    two = true;
                }
                if (s.count({h[i]+j-i, h[i]+j})) {
                    ans++;
                }
            }
            if (s.count({j-i, h[i]+i}) and h[i]+i==h[j]+j and !two) {
                ans++;
            }
            if (s.count({j-i, h[i]+j}) and h[j]+i==h[i]+j and !one){
                ans++;
            }
        }
    }
    return ans;
}

int maxn = 5, big = 0;
vector <int> ans;

void call(vector <int> v) {
    if (v.size()==maxn) {
        int num = 0;
        for (int i = 0; i < maxn; i++) {
            for (int j = i+1; j < maxn; j++) {
                for (int k = j+1; k < maxn; k++) {
                    if (j>=maxn or k>= maxn) {
                        break;
                    }
                    vector <int> v1, v2;
                    v1.push_back(j-i);
                    v1.push_back(k-i);
                    v1.push_back(k-j);
                    v2.push_back(v[i]);
                    v2.push_back(v[j]);
                    v2.push_back(v[k]);
                    sort(v1.begin(), v1.end());
                    sort(v2.begin(), v2.end());
                    if (v1[0]==v2[0] and v1[1]==v2[1] and v1[2]==v2[2]) {
                        num++;
                    }
                }
            }
        }
        if (num>big) {
            ans=vector <int> (maxn);
            for (int i = 0; i < maxn; i++) {
                ans[i]=v[i];
            }
            big = num;
        }
    } else {
        for (int i = 1; i <= maxn-1; i++) {
            vector <int> vs;
            for (int j = 0; j < v.size(); j++) {
                vs.push_back(v[j]);
            }
            vs.push_back(i);
            call(vs);
        }
    }
}

std::vector<int> construct_range(int m, int k) {
    call({});
    cout << big << endl;
    for (int i = 0; i < maxn; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return {1};
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 6
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 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