Submission #199590

#	Time	Username	Problem	Language	Result	Execution time	Memory
199590		SamAnd	Drvca (COCI19_drvca)	C++17	110 / 110	56 ms	6512 KiB

drvca

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n;
int a[N];

void stg(const vector<int>& v1, const vector<int>& v2)
{
    if (v1.empty())
        return;
    if (v2.empty())
        return;
    for (int i = 0; i < v1.size() - 1; ++i)
    {
        if (v1[i + 1] - v1[i] != v1[1] - v1[0])
            return;
    }
    for (int i = 0; i < v2.size() - 1; ++i)
    {
        if (v2[i + 1] - v2[i] != v2[1] - v2[0])
            return;
    }
    printf("%d\n", v1.size());
    for (int i = 0; i < v1.size(); ++i)
        printf("%d ", v1[i]);
    printf("\n");
    printf("%d\n", v2.size());
    for (int i = 0; i < v2.size(); ++i)
        printf("%d ", v2[i]);
    printf("\n");
    exit(0);
}

vector<int> v1, v2;
void rec(int i)
{
    if (i == n + 1)
    {
        stg(v1, v2);
        return;
    }
    if (v1.size() >= 2 && v1[1] - v1[0] == a[i] - v1.back())
    {
        v1.push_back(a[i]);
        rec(i + 1);
        v1.pop_back();
        return;
    }
    if (v2.size() >= 2 && v2[1] - v2[0] == a[i] - v2.back())
    {
        v2.push_back(a[i]);
        rec(i + 1);
        v2.pop_back();
        return;
    }
    if (v1.size() <= 1)
    {
        v1.push_back(a[i]);
        rec(i + 1);
        v1.pop_back();
    }
    if (v2.size() <= 1)
    {
        v2.push_back(a[i]);
        rec(i + 1);
        v2.pop_back();
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    rec(1);
    printf("-1\n");
    return 0;
    v1.push_back(a[1]);
    v1.push_back(a[2]);
    for (int i = 3; i <= n; ++i)
    {
        if (a[i] - v1.back() == a[2] - a[1])
            v1.push_back(a[i]);
        else
            v2.push_back(a[i]);
    }
    stg(v1, v2);
    v1.clear();
    v2.clear();
    v1.push_back(a[1]);
    v2.push_back(a[2]);
    if (n == 2)
        stg(v1, v2);
    v1.push_back(a[3]);
    for (int i = 4; i <= n; ++i)
    {
        if (a[i] - v1.back() == a[3] - a[1])
            v1.push_back(a[i]);
        else
            v2.push_back(a[i]);
    }
    stg(v1, v2);
    v1.clear();
    v2.clear();
    v1.push_back(a[1]);
    v2.push_back(a[2]);
    v2.push_back(a[3]);
    for (int i = 4; i <= n; ++i)
    {
        if (a[i] - v2.back() == a[3] - a[2])
            v2.push_back(a[i]);
        else
            v1.push_back(a[i]);
    }
    stg(v1, v2);
    printf("-1\n");
    return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'void stg(const std::vector<int>&, const std::vector<int>&)':
drvca.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v1.size() - 1; ++i)
                     ~~^~~~~~~~~~~~~~~
drvca.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v2.size() - 1; ++i)
                     ~~^~~~~~~~~~~~~~~
drvca.cpp:24:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", v1.size());
                    ~~~~~~~~~^
drvca.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v1.size(); ++i)
                     ~~^~~~~~~~~~~
drvca.cpp:28:29: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", v2.size());
                    ~~~~~~~~~^
drvca.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v2.size(); ++i)
                     ~~^~~~~~~~~~~
drvca.cpp: In function 'int main()':
drvca.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
drvca.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30