Submission #1002688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002688		aykhn	Watermelon (INOI20_watermelon)	C++17	100 / 100	70 ms	22864 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define inf 0x3F3F3F3F

const int MXN = 1e5 + 5;
const int LOG = 20;

vector<int> adj[MXN];
int used[MXN];
int cyc = 0;

void dfs(int a)
{
  used[a] = 1;
  for (int &v : adj[a])
  {
    if (!used[v]) dfs(v);
    else if (used[v] == 1)
    {
      cyc = 1;
    }
  }
  used[a] = 2;
}

int n, k;
vector<int> perm, res;
int deg[MXN];
set<int> s;
int cnt = 0;


void findkth()
{
  if (perm.size() == n)
  {
    if (++cnt == k) res = perm;
    return;
  }
  for (int i = 0; i < s.size(); i++)
  {
    auto it = s.begin();
    for (int j = 0; j < i; j++) it++;
    int x = *it;
    perm.push_back(x);
    s.erase(it);
    vector<int> tmp;
    for (int &v : adj[x]) 
    {
      if (--deg[v] == 0) s.insert(v);
    }
    findkth();
    if (!res.empty()) return;
    perm.pop_back();
    s.insert(x);
    for (int &v : adj[x])
    {
      if (deg[v]++ == 0) s.erase(v);
    }
  }
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  int a[n + 1];
  for (int i = 1; i <= n; i++) cin >> a[i];
  if (a[n] != -1)
  {
    cout << -1 << '\n';
    return 0;
  }
  for (int i = 1; i <= n; i++)
  {
    if (a[i] == -1) a[i] = inf + n - i;
  }
  vector<int> v;
  for (int i = n; i >= 1; i--)
  {
    int mx = 0;
    while (!v.empty() && a[v.back()] < a[i])
    {
      adj[v.back()].push_back(i);
      deg[i]++;
      mx = max(mx, a[v.back()]);
      v.pop_back();
    }
    if (a[i] <= n && mx + 1 != a[i])
    {
      cout << -1 << '\n';
      return 0;
    }
    if (!v.empty())
    {
      adj[i].push_back(v.back());
      deg[v.back()]++;
      if (a[v.back()] == a[i]) v.pop_back();
    } 
    v.push_back(i);
  }
  for (int i = 1; i <= n; i++) if (!used[i]) dfs(i);
  if (cyc)
  {
    cout << -1 << '\n';
    return 0;
  }
  for (int i = 1; i <= n; i++) if (!deg[i]) s.insert(i);
  findkth();
  if (res.empty())
  {
    cout << -1 << '\n';
    return 0;
  }
  int ans[n + 1];
  for (int i = 0; i < n; i++) ans[res[i]] = i + 1;
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  cout << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void findkth()':
Main.cpp:37:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if (perm.size() == n)
      |       ~~~~~~~~~~~~^~~~
Main.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for (int i = 0; i < s.size(); i++)
      |                   ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 25 / 25
• Subtask 3: 31 / 31
• Subtask 4: 18 / 18
• Subtask 5: 19 / 19