Submission #1047183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047183		sofijavelkovska	Art Collections (BOI22_art)	C++17	50 / 100	387 ms	1296 KiB

art

#include "art.h"
//#include "sample_grader.cpp"

#include <bits/stdc++.h>
using namespace std;

vector<int> sorted;
int inv;

bool smaller(int x, int y)
{
    swap(sorted[x-1], sorted[y-1]);
    int newinv=publish(sorted);
    swap(sorted[x-1], sorted[y-1]);
    if (x<y && inv<newinv)
        return true;
    if (x>y && inv>newinv)
        return true;

    return false;
}

vector<int> mergesort(vector<int> a)
{
    int n=a.size();
    if (n==1)
        return a;
    vector<int> left, right;
    for (int i=0; i<n/2; i++)
        left.push_back(a[i]);
    for (int i=n/2; i<n; i++)
        right.push_back(a[i]);
    a.clear();
    left=mergesort(left);
    right=mergesort(right);
    reverse(left.begin(), left.end());
    reverse(right.begin(), right.end());
    while (a.size()<n)
    {
        if (right.empty() || (!left.empty() && smaller(left.back(), right.back())))
        {
            a.push_back(left.back());
            left.pop_back();
        }
        else
        {
            a.push_back(right.back());
            right.pop_back();
        }
    }

    return a;
}

void solve(int n)
{
    vector<int> a(n);
    for (int i=0; i<n; i++)
        a[i]=i+1;
    sorted.resize(n);
    for (int i=0; i<n; i++)
        sorted[i]=i+1;
    inv=publish(a);
    answer(mergesort(a));

    return;
}

Compilation message (stderr)

art.cpp: In function 'std::vector<int> mergesort(std::vector<int>)':
art.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |     while (a.size()<n)
      |            ~~~~~~~~^~
interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30