oj.uz

Submission #679609

# Submission time Handle Problem Language Result Execution time Memory
679609 2023-01-08T16:31:55 Z speedyArda Gondola (IOI14_gondola) C++14
100 / 100
 93 ms 11856 KB 
#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
//int freq[250005];
map<ll, ll> freq;
int used[250005];
int reve[250005];
const ll MOD = 1e9+9;
ll binpow(ll x, ll y)
{
  ll ans = 1;
  while(y > 0)
  {
    if(y & 1)
      ans = ans * x % MOD;
    x = x * x % MOD;
    y >>= 1;
  }
  return ans;
}

int valid(int n, int inputSeq[])
{
  if(n == 1)
    return 1;
  vector<pair<int, int> > originals;
  set<int> elems;
  for(int i = 0; i < n; i++)
  {
      elems.insert(i + 1);
      if(freq[inputSeq[i]] > 0)
        return 0;
      freq[inputSeq[i]]++;
      if(inputSeq[i] <= n)
      {
        originals.push_back({inputSeq[i], i});
      }
      
        
  }
  if(originals.size() <= 1) // All elements or n-1 elements are changed, so valid
    return 1; 
  int res = 1;
  originals.push_back({originals[0].first, originals[0].second + n});
  elems.erase(originals[0].first);
  int curr = (originals[0].first + 1) % (n+1), idx = originals[0].second + 1;
  if(curr == 0)
    curr++;
  for(int i = 1; i < originals.size(); i++)
  {
    //cout << res << "\n";
    while(idx < originals[i].second)
    {
      if(elems.find(curr) == elems.end())
        res = 0;
      elems.erase(curr);
      curr = (curr + 1) % (n+1);
      if(curr == 0)
        curr++;
      idx++;
    }
    

    if(curr != originals[i].first)
      res = 0;
    //elems.erase(originals[i].first);
    if(i + 1 != originals.size())
    {
      if(elems.find(originals[i].first) == elems.end())
        res = 0;
      elems.erase(originals[i].first);
    }
    //cout << res << " " << idx << " " << curr << " " << originals[i].first << "\n";
    idx++;
     curr = (curr + 1) % (n+1);
      if(curr == 0)
        curr++;
  }
  return res;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{

  int biggest = 0;
  set<int> can_be_used;
  vector<pair<int, int> > originals;
  for(int i = 0; i < n; i++)
  {
    can_be_used.insert(i + 1);
    biggest = max(biggest, gondolaSeq[i]);

    if(gondolaSeq[i] <= n)
      originals.push_back({gondolaSeq[i], i});
    //used[gondolaSeq[i]] = i;
  }
  int idx = 0, curr = 1, finishidx = -1;
  if(originals.size() > 0) // There is nonchanged element we can use for reference. Since gondolaseq is already valid (the questions states) we can assume this will provide a true intiial array (1 ..... n)
  {
    finishidx = originals[0].second;
    idx = (originals[0].second + 1) % n;
    curr = (originals[0].first + 1) % (n + 1);
    used[originals[0].first] = originals[0].first;
    reve[originals[0].first] = originals[0].first;
    if(curr == 0)
      curr++;
  }
  while(idx < n)
  {
    used[gondolaSeq[idx]] = curr;
    reve[curr] = gondolaSeq[idx];
    //if(idx == 47)
      //cout << gondolaSeq[idx] << " " << curr << " " << used[gondolaSeq[idx]] << "\n";
    curr = (curr + 1) % (n+1);
    if(curr == 0)
      curr++;
    idx++;
      
  }
  idx = 0;
  while(idx < finishidx)
  {
    used[gondolaSeq[idx]] = curr;
    reve[curr] = gondolaSeq[idx];
    curr = (curr + 1) % (n+1);
      if(curr == 0)
        curr++;
    idx++;
  }
  //cout << used[1] << "\n";
  int last = used[biggest];
  int now = n + 1;
  idx = 0;
  for(int i = 1; i <= biggest; i++)
  {
    if(i > n && (used[i] == 0 || i == biggest))
    {
      replacementSeq[idx] = last;
      last = now;
      now++;
      idx++;
    } else if(i > n)
    {
      replacementSeq[idx] = used[i];
      now++;
      idx++;
    }
  }
  
  return biggest - n;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
  ll ans = 1;
  if(valid(n, inputSeq) == 0)
    return 0;
  ll cnt = n;
  sort(inputSeq, inputSeq + n);
  ll last = n;
  for(int i = 0; i < n; i++)
  {
      if(inputSeq[i] <= n) {
        //last = inputSeq[i];
        cnt--;
        continue;
      } else 
      {
        ans = (ans) * binpow(cnt, (ll)(inputSeq[i] - last - 1)) % MOD;

        last = inputSeq[i];
        cnt--;
      }
  }
  if(inputSeq[0] > n) // All elements are changed So we can have multiple initial orders
  {
    ans = ans * (ll)n % MOD;
  }
  return ans % MOD;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 1; i < originals.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
gondola.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     if(i + 1 != originals.size())
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 26 ms 4824 KB Output is correct
7 Correct 10 ms 724 KB Output is correct
8 Correct 52 ms 8888 KB Output is correct
9 Correct 13 ms 3024 KB Output is correct
10 Correct 53 ms 10312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 22 ms 4792 KB Output is correct
7 Correct 10 ms 632 KB Output is correct
8 Correct 46 ms 8896 KB Output is correct
9 Correct 15 ms 3088 KB Output is correct
10 Correct 56 ms 10344 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 24 ms 4308 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 93 ms 10508 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 24 ms 5476 KB Output is correct
12 Correct 29 ms 6248 KB Output is correct
13 Correct 16 ms 3348 KB Output is correct
14 Correct 30 ms 5440 KB Output is correct
15 Correct 19 ms 3404 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 74 ms 8652 KB Output is correct
10 Correct 49 ms 7332 KB Output is correct
11 Correct 16 ms 2772 KB Output is correct
12 Correct 20 ms 3412 KB Output is correct
13 Correct 5 ms 980 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 73 ms 8672 KB Output is correct
10 Correct 52 ms 7368 KB Output is correct
11 Correct 16 ms 2772 KB Output is correct
12 Correct 21 ms 3428 KB Output is correct
13 Correct 4 ms 1076 KB Output is correct
14 Correct 73 ms 10596 KB Output is correct
15 Correct 87 ms 11856 KB Output is correct
16 Correct 13 ms 2348 KB Output is correct
17 Correct 50 ms 8040 KB Output is correct
18 Correct 25 ms 4660 KB Output is correct