Submission #412996

#	Time	Username	Problem	Language	Result	Execution time	Memory
412996		Ozy	Group Photo (JOI21_ho_t3)	C++17	0 / 100	1 ms	204 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl
#define debugarr(x,a,b) cout << #x << " = ["; rep(iii, a, b) cout << x[iii] << ", "; cout << "]\n"

#define MAX 5000

lli n,res,pos,ant,ult,a,b, ind, mi, md, indi, indd, pi, pd;
lli arr[MAX+2],dir[MAX+2];
vector<lli> sol;

bool correcto(lli pos, lli x){
    return pos >= sol.size() || sol[pos] == x - 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n) cin >> arr[i];

    sol.push_back(1);

    rep(act,2,n) {
        ult = 0;
        rep(i,1,n){
            if (arr[i] < act) ult = arr[i];
            if (arr[i] == act) {
                pos = i;
                break;
            }
        }

        if (!ult) ind = 0;
        else{
            rep(i, 0, sol.size() - 1) if (sol[i] == ult){
                ind = i + 1;
                break;
            }
        }
        // IND TIENE EL PRIMER ELEMENTO DE LOS MENORES DESPUES QUE EL

        indi = mi = pi = -10000000;
        repa(i, ind, 0) if (correcto(i, act)){
            indi = i;
            if (indi < sol.size()) mi = sol[i];
            break;
        }
        if (indi == sol.size()){
            sol.push_back(act);
            continue;
        }


        rep(i, ind + 1, sol.size()) if (correcto(i, act)){
            indd = i - 1;
            md = sol[i - 1];
            break;
        }

        rep(i, 1, n) if (arr[i] == mi){ pi = i; break; }
        rep(i, 1, n) if (arr[i] == md){ pd = i; break; }


        if (pi > pos){
            sol.push_back(act);
            repa(i, sol.size() - 1, 1){
                swap(sol[i], sol[i - 1]);
                if (sol[i] == mi) break;
            }
            continue;
        }

        if (pos - pi <= pd - pos){
            repa(i, pos, pi + 1) swap(arr[i], arr[i - 1]);
            res += pos - pi;
            sol.push_back(act);
            repa(i, sol.size() - 1, 1){
                swap(sol[i], sol[i - 1]);
                if (sol[i] == mi) break;
            }
        }
        else {
            rep(i, pos, pd - 1) swap(arr[i], arr[i + 1]);
            res += pd - pos;
            sol.push_back(act);
            repa(i, sol.size() - 1, 1){
                swap(sol[i], sol[i - 1]);
                if (sol[i] == md){
                    swap(sol[i], sol[i - 1]);
                    break;
                }
            }
        }

    }

    cout << res;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool correcto(long long int, long long int)':
Main.cpp:18:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     return pos >= sol.size() || sol[pos] == x - 1;
      |            ~~~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Main.cpp:43:13: note: in expansion of macro 'rep'
   43 |             rep(i, 0, sol.size() - 1) if (sol[i] == ult){
      |             ^~~
Main.cpp:53:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (indi < sol.size()) mi = sol[i];
      |                 ~~~~~^~~~~~~~~~~~
Main.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (indi == sol.size()){
      |             ~~~~~^~~~~~~~~~~~~
Main.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Main.cpp:62:9: note: in expansion of macro 'rep'
   62 |         rep(i, ind + 1, sol.size()) if (correcto(i, act)){
      |         ^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36