oj.uz

Submission #258414

# Submission time Handle Problem Language Result Execution time Memory
258414 2020-08-05T22:53:26 Z ipaljak Slagalica (COCI19_slagalica2) C++14
70 / 70
 55 ms 3020 KB 
#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

typedef long long llint;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 10;

bool l, r;
bool ll[4] = {1, 0, 1, 0};

int n, fst, lst;
int cnt[4];

priority_queue<int, vector<int>, greater<int>> puzzle[4];

bool ok(bool left, bool right) {
  if (abs(cnt[0] - cnt[3]) > 1) return false;
  if (left != right && abs(cnt[0] - cnt[3]) == 1) return false;
  if (left == right && left && cnt[3] <= cnt[0]) return false;
  if (left == right && !left && cnt[0] <= cnt[3]) return false;
  if (cnt[0] + cnt[3] == 0 && left && cnt[1] > 0) return false;
  if (cnt[0] + cnt[3] == 0 && !left && cnt[2] > 0) return false;
  return true;
}

int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int x, a;
    scanf("%d%d", &x, &a); --x;
    if (x < 4) puzzle[x].push(a), ++cnt[x];
    l |= x == 4;
    r |= x == 6;
    fst += a * (x == 4 || x == 5);
    lst += a * (x == 6 || x == 7);
  }

  if (!ok(l, r)) {
    printf("-1\n");
    return 0;
  }

  printf("%d ", fst);

  for (int i = 0; i < n - 2; ++i) {
    int pivot = -1, best = MOD;
    for (int j = 0; j < 4; ++j) {
      if (puzzle[j].empty()) continue;
      --cnt[j];
      if (ok(ll[j], r) && puzzle[j].top() < best)
        pivot = j, best = puzzle[j].top();
      ++cnt[j];
    }

    printf("%d ", best);
    puzzle[pivot].pop();
    --cnt[pivot]; l = ll[pivot];
  }

  printf("%d\n", lst);
  return 0;
}

Compilation message

slagalica.cpp: In function 'int main()':
slagalica.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
slagalica.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &a); --x;
     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2592 KB Output is correct
2 Correct 26 ms 1948 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2612 KB Output is correct
2 Correct 24 ms 1908 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2036 KB Output is correct
2 Correct 48 ms 2956 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1920 KB Output is correct
2 Correct 50 ms 2644 KB Output is correct
3 Correct 53 ms 2972 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2676 KB Output is correct
2 Correct 26 ms 1916 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2544 KB Output is correct
2 Correct 26 ms 1916 KB Output is correct
3 Correct 49 ms 2868 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1920 KB Output is correct
2 Correct 46 ms 2564 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3020 KB Output is correct
2 Correct 24 ms 1792 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2552 KB Output is correct
2 Correct 26 ms 1792 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3020 KB Output is correct
2 Correct 27 ms 1912 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2772 KB Output is correct
2 Correct 24 ms 1920 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2636 KB Output is correct
2 Correct 27 ms 1920 KB Output is correct