Submission #1013083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013083		vjudge1	Slagalica (COCI19_slagalica2)	C++17	70 / 70	52 ms	3480 KiB

slagalica

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5