oj.uz

Submission #1002620

# Submission time Handle Problem Language Result Execution time Memory
1002620 2024-06-19T17:02:46 Z vjudge1 Watermelon (INOI20_watermelon) C++17
0 / 100
 18 ms 12124 KB 
#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--)
  {
    while (!v.empty() && a[v.back()] < a[i])
    {
      adj[v.back()].push_back(i);
      deg[i]++;
      v.pop_back();
    }
    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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2580 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2580 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12120 KB Output is correct
2 Incorrect 18 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12120 KB Output is correct
2 Incorrect 18 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2580 KB Output is correct
4 Incorrect 1 ms 2652 KB Output isn't correct
5 Halted 0 ms 0 KB -