Submission #1101542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101542		vjudge1	Slagalica (COCI19_slagalica2)	C++17	15 / 70	27 ms	3148 KiB

slagalica

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define OUTIE true
#define INNIE false
using namespace std;
using ll = long long;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

constexpr int MAX_N = 1E5 + 5;

bool flag, last;
int N, X[MAX_N], A[MAX_N];
signed leftOutie, rightOutie, leftInnie, rightInnie, result[MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pieces[2][2];

signed main() {

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N;

    fort(i, 1, N) {
        cin >> X[i] >> A[i];
        if (X[i] == 1) {
            pieces[OUTIE][OUTIE].emplace(A[i], i);
            ++leftOutie;
            ++rightOutie;
        } else if (X[i] == 2) {
            pieces[OUTIE][INNIE].emplace(A[i], i);
            ++leftOutie;
            ++rightInnie;
        } else if (X[i] == 3) {
            pieces[INNIE][OUTIE].emplace(A[i], i);
            ++leftInnie;
            ++rightOutie;
        } else if (X[i] == 4) {
            pieces[INNIE][INNIE].emplace(A[i], i);
            ++leftInnie;
            ++rightInnie;
        } else if (X[i] == 5) {
            result[1] = A[i];
            ++rightOutie;
            flag = OUTIE;
        } else if (X[i] == 6) {
            result[1] = A[i];
            ++rightInnie;
            flag = INNIE;
        } else if (X[i] == 7) {
            result[N] = A[i];
            ++leftOutie;
            last = OUTIE;
        } else if (X[i] == 8) {
            result[N] = A[i];
            ++leftInnie;
            last = INNIE;
        }
    }

    if (rightOutie != leftInnie || rightInnie != leftOutie) {
        cout << -1 << '\n';
        return 0;
    }

    fore(i, 2, N) {

        const bool x = !flag;
        int which = -1, what = -1;

        if (flag == OUTIE)
            --rightOutie;
        else
            --rightInnie;

        if (x == OUTIE)
            --leftOutie;
        else
            --leftInnie;

        fort(y, 0, 1) {
            if (pieces[x][y].empty() ||
                i + 1 < N && (y == OUTIE && last == INNIE && rightOutie == 1 ||
                              y == INNIE && last == OUTIE && rightInnie == 1))
                continue;
                const auto &[a, it] = pieces[x][y].top();
                if (which < 0 || A[which] > a) {
                    which = it;
                    what = y;
                }
            }

        if (which < 0) {
            cout << -1 << '\n';
            return 0;
        }

        flag = what;
        result[i] = A[which];
        pieces[x][what].pop();
    }

    fort(i, 1, N)
        cout << result[i] << ' ';
    cout << '\n';

    return 0;
}

Compilation message (stderr)

slagalica.cpp: In function 'int main()':
slagalica.cpp:131:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  131 |                 i + 1 < N && (y == OUTIE && last == INNIE && rightOutie == 1 ||
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
slagalica.cpp:131:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  131 |                 i + 1 < N && (y == OUTIE && last == INNIE && rightOutie == 1 ||
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  132 |                               y == INNIE && last == OUTIE && rightInnie == 1))
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
slagalica.cpp:130:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  130 |             if (pieces[x][y].empty() ||
      |             ^~
slagalica.cpp:134:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  134 |                 const auto &[a, it] = pieces[x][y].top();
      |                 ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5