Программа не проходит по времени , несмотря на низкие ограничения

Question

https://acmp.ru/asp/do/index.asp?main=task&id_course=3&id_section=22&id_topic=276&id_problem=1801 - задача с acmp.

Решение вроде работает , но не проходит по времени , хотя ограничения небольшие и перебор должен проходить

Не подскажите , в чём проблема , или как оптимизировать решение ?


#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define fo(i,start,n,step) for(int  i = start; i < n; i+=step)
#define cd cin >> a[i];
#define ends cout << "\n";
#define pb(val) push_back(val);


    struct point {
        int a;
        int b;
        int c;
        int d;
    };

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<point> p(k);
    fo(i,0,k,1)  {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        point po;
        po.a = a;
        po.b = b;
        po.c = c;
        po.d = d;
        p[i] = po;
    }
    vector<int> tr(n);
    fo(i, 1, n+1, 1) {
        tr[i-1] = i;
    }
        do {
            vector<int> a(n + 1);

        fo(i,0,n,1) {
            a[tr[i]] = i;
        }
            int realres = 0;
            fo(i, 0, k, 1) {
                int sum = 0;
                if (a[p[i].a] > a[p[i].b]) {
                    sum++;
                }
                if (a[p[i].c] > a[p[i].d]) {
                    sum++;
                }
                if (sum == 1) {
                    realres++;
                } else break;
            }
            if (realres == k) {
                for (int x : tr) cout << x << " ";
                return 0;
            }
        }
    while (std::next_permutation(tr.begin(),tr.end()));

    cout << 0;

    return 0;
}

Answer 1

Короче говоря, чтоб проскочить, оказалось достаточным отсортировать и выбросить одинаковые ставки. Не гонюсь за краткостью, тут вам карты в руки :), у меня как раз удлиннения, лишь бы понятнее было :)

Вот код, который прошел все тесты:

#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;


struct bet
{
    int a, b, c, d;
};

bool operator<(const bet&a,const bet&b)
{
    return tie(a.a,a.b,a.c,a.d) < tie(b.a,b.b,b.c,b.d);
}
bool operator==(const bet&a,const bet&b)
{
    return tie(a.a,a.b,a.c,a.d) == tie(b.a,b.b,b.c,b.d);
}

int main()
{
    int k,n;
    cin >> k >> n;
    int s[] = { 0,1,2,3,4,5,6,7,8,9 };
    vector<bet> v;
    v.reserve(n);
    for(int i = 0; i < n; ++i)
    {
        bet x;
        cin >> x.a >> x.b >> x.c >> x.d;
        x.a--; x.b--; x.c--; x.d--;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    int pos[10];

    do {
        for(int i = 0; i < k; ++i) pos[s[i]]=i;
        bool ok = true;
        for(int i = 0; i < n; ++i)
        {
            bet&b = v[i];
            int t = pos[b.a] < pos[b.b];
            int u = pos[b.c] < pos[b.d];
            if (t+u != 1) { ok = false; break; }
        }
        if (!ok) continue;
        for(int i = 0; i < k; ++i) cout << (s[i]+1) << " "; cout << endl;
        return 0;

    } while(next_permutation(s,s+k));

    cout << "0\n";
}

P.S. Если бы не прошел - следующим шагом я бы искал противоречия в ставках...

БЛОГ НА HUSL

Программа не проходит по времени , несмотря на низкие ограничения

Ответы (1 шт):