제출 #1352256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1352256		d4n13l	3개의 봉우리 (IOI25_triples)	C++20	25.89 / 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 = 9, big = 0;
vector <int> ans;

void call(vector <int> v) {
    if (v.size()>0 and v[0]>1) {
        return;
    }
    if (v.size()>1 and v[1]>2) {
        return;
    }
    if (v.size()==maxn) {
        ll x = count_triples(v);
        if (x>big) {
            ans=vector <int> (maxn);
            for (int i = 0; i < maxn; i++) {
                ans[i]=v[i];
            }
            big = x;
        }
    } 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);
        }
    }
}

vector <int> v= {1, 1, 2, 3, 4, 1, 2, 1, 3};

std::vector<int> construct_range(int m, int k) {
    //call({});
    //cout << big << endl;
    vector <int> an;
    for (int i = 0; i < m; i++) {
        an.push_back(v[i%9]);
        //cout << v[i%9] << " ";
    }
    //cout << endl;
    return an;
}

• 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: 4.3333 / 5
• Subtask 8: 1.9325 / 5
• Subtask 9: 0.7773 / 5
• Subtask 10: 0.3333 / 5
• Subtask 11: 0.3889 / 5
• Subtask 12: 0.1296 / 5