oj.uz

Submission #1013083

# Submission time Handle Problem Language Result Execution time Memory
1013083 2024-07-03T07:22:09 Z vjudge1 Slagalica (COCI19_slagalica2) C++17
70 / 70
 52 ms 3480 KB 
#include<bits/stdc++.h>

using namespace std;

int cnt[9] = {};
vector<int> v[9], G[9];

bool check()
{
  bool ans = true;
  ans &= (cnt[1] <= cnt[4] + cnt[3] + cnt[8]);
  ans &= (cnt[4] <= cnt[1] + cnt[2] + cnt[7]);
  if(cnt[2])
    ans &= (cnt[1] + cnt[7] >= 1);
  if(cnt[3])
    ans &= (cnt[4] + cnt[8] >= 1);
  ans &= (cnt[7] + cnt[8] == 1);
  ans &= *min_element(cnt, cnt + 9) >= 0; 
  return ans;
}

int main()
{
  int n;
  cin >> n;

  G[1] = {3, 4, 8};
  G[2] = {1, 2, 7};
  G[3] = {8, 3, 4};
  G[4] = {1, 2, 7};
  G[5] = {3, 4, 8};
  G[6] = {1, 2, 7};
  
  
  for(int i = 0; i < n; i ++)
    {
      int x, a;
      cin >> x >> a;
      v[x].push_back(a);
      cnt[x]++;
    }
  

  for(int i = 1; i <= 8; i ++)
    sort(v[i].rbegin(), v[i].rend());

  if(v[5].size() + v[6].size() != 1)
    {
      cout << -1 << endl;
      return 0;
    }

  if(!check())
    {
      cout << -1 << endl;
      return 0;
    }

  int cur;
  vector<int> ans;
  if(v[5].size() == 1)
    cur = 5, ans.push_back(v[5][0]);
  else
    cur = 6, ans.push_back(v[6][0]);

  cnt[5] = cnt[6] = 0;
  // cerr << "done\n";
  for(int i = 1; i + 1 < n; i ++)
    {
      
      int nxt = -1;
      for(int k : G[cur])
	{
	  // cerr << "k = " << k << endl;
	  cnt[k]--;
	  if(check())
	    nxt = (nxt == -1 || v[nxt].back() > v[k].back()) ? k : nxt;
	  cnt[k]++;
	}
      // cerr << nxt << endl;
      if(nxt == -1)
	{
	  cout << nxt << endl;
	  return 0;
	}

      cnt[nxt]--;
      ans.push_back(v[nxt].back());
      v[nxt].pop_back();
      cur = nxt;
    }

  for(int i : G[cur])
    if(i == 7 || i == 8)
      ans.push_back(v[i][0]);

  if(ans.size() != n)
    cout << -1;
  else
    for(int i : ans)
      cout << i << ' ';
  cout << endl;
  return 0;
}

Compilation message

slagalica.cpp: In function 'int main()':
slagalica.cpp:97:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if(ans.size() != n)
      |      ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2916 KB Output is correct
2 Correct 37 ms 1924 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2828 KB Output is correct
2 Correct 33 ms 1948 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1996 KB Output is correct
2 Correct 52 ms 3144 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1916 KB Output is correct
2 Correct 43 ms 2896 KB Output is correct
3 Correct 46 ms 3444 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2888 KB Output is correct
2 Correct 31 ms 2040 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2828 KB Output is correct
2 Correct 37 ms 2124 KB Output is correct
3 Correct 45 ms 3168 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2256 KB Output is correct
2 Correct 42 ms 3016 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 3480 KB Output is correct
2 Correct 36 ms 2264 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3088 KB Output is correct
2 Correct 36 ms 2256 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3336 KB Output is correct
2 Correct 41 ms 2512 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3016 KB Output is correct
2 Correct 42 ms 2512 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3016 KB Output is correct
2 Correct 37 ms 2516 KB Output is correct