oj.uz

Submission #1101542

# Submission time Handle Problem Language Result Execution time Memory
1101542 2024-10-16T09:42:54 Z vjudge1 Slagalica (COCI19_slagalica2) C++17
15 / 70
 27 ms 3148 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3148 KB Output is correct
2 Correct 15 ms 3056 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3120 KB Output is correct
2 Correct 14 ms 3016 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2244 KB Output is correct
2 Incorrect 20 ms 2244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1992 KB Output is correct
2 Correct 24 ms 3020 KB Output is correct
3 Incorrect 20 ms 2416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3020 KB Output is correct
2 Correct 12 ms 1988 KB Output is correct
3 Incorrect 22 ms 2212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2108 KB Output is correct
2 Incorrect 20 ms 2252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 2524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2000 KB Output isn't correct
2 Halted 0 ms 0 KB -