Submission #608961

#	Time	Username	Problem	Language	Result	Execution time	Memory
608961		Duy_e	Monster Game (JOI21_monster)	C++17	0 / 100	58 ms	432 KiB

monster

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

const long long N = 2e2 + 5;vector <int> save;

void rec(int l, int r, vector <int> &v) {
    if (l >= r) return;
    int pivot = l + rand() % (r - l + 1);
    vector <int> lef, rig;
    save.push_back(v[pivot]);

    
    for (int i = l; i <= r; i ++) if (i != pivot) {
        if (Query(v[pivot], v[i])) 
            lef.push_back(v[i]);
        else 
            rig.push_back(v[i]);
    }

    lef.push_back(v[pivot]);
    for (int i: rig) lef.push_back(i);

    int mid = 0;
    pivot = v[pivot];
    for (int i = 0; i < (r - l + 1); i ++) {
        if (lef[i] == pivot) mid = l + i;
        v[l + i] = lef[i];
    }
    rec(l, mid - 1, v); rec(mid + 1, r, v);
}

vector<int> Solve(int n) {

  	vector<int> T(n);

    for (int i = 0; i < n; i ++) T[i] = i;

    rec(0, n - 1, T);

    reverse(save.begin(), save.end());
    for (int pivot: save) {
        for (int i = 0; i < n; i ++)
            if (T[i] == pivot) {
                if (i == 0) {
                    int l = i + 1, r = i + 2;
                    if (Query(T[i], T[r])) swap(T[i], T[r]);
                    break;
                }

                if (i == n - 1) {
                    int l = i - 2, r = i - 1;
                    if (Query(T[l], T[i])) swap(T[l], T[i]);
                    break;
                }

                if (true) {
                    int l = i - 1, r = i + 1;
                    if (Query(T[l], T[r])) swap(T[l], T[r]);
                }
            } 
    }

    vector <int> ret(n);
    for (int i = 0; i < n; i ++) {
        ret[T[i]] = i;
    }


	return ret;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:46:25: warning: unused variable 'l' [-Wunused-variable]
   46 |                     int l = i + 1, r = i + 2;
      |                         ^
monster.cpp:52:36: warning: unused variable 'r' [-Wunused-variable]
   52 |                     int l = i - 2, r = i - 1;
      |                                    ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75