oj.uz

Submission #389157

# Submission time Handle Problem Language Result Execution time Memory
389157 2021-04-13T18:16:57 Z apostoldaniel854 Gondola (IOI14_gondola) C++14
100 / 100
 69 ms 6020 KB 
#include <bits/stdc++.h>


using namespace std;

//#define HOME

#ifndef HOME
#include "gondola.h"
#endif // HOME

int valid(int n, int inputSeq[]) {
    int mn = 0;
    map <int, int> freq;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] < inputSeq[mn])
            mn = i;
        freq[inputSeq[i]]++;
        if (freq[inputSeq[i]] > 1) return 0;
    }
    rotate (inputSeq, inputSeq + mn, inputSeq + n);
    int val = inputSeq[0];
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] <= n) {
            if (val != inputSeq[i])
                return 0;
        }
        val++;
    }
    return 1;
}

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

const int max_n = 25e4;

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int mn = 0;
    for (int i = 0; i < n; i++) {
        if (gondolaSeq[i] < gondolaSeq[mn])
            mn = i;
    }
    if (gondolaSeq[mn] <= n)
        rotate (gondolaSeq, gondolaSeq + (n + mn - gondolaSeq[mn] + 1) % n, gondolaSeq + n);
    int l = 0;
    vector <int> pos (1 + max_n);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        pos[gondolaSeq[i]] = i + 1;
        if (gondolaSeq[i] > gondolaSeq[mx])
            mx = i;
    }
    int valmax = gondolaSeq[mx];
    int cur = mx + 1;
    for (int i = n + 1; i <= valmax; i++) {
        if (i == valmax || pos[i] == 0)
            replacementSeq[l++] = cur, cur = i;
        else
            replacementSeq[l++] = pos[i];
    }
    return l;
}

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

const int MOD = 1e9 + 9;

int mult (int a, int b) {
    return 1ll * a * b % MOD;
}

int lgput (int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b & 1)
            ans = mult (ans, a);
        a = mult (a, a);
        b /= 2;
    }
    return ans;
}

int countReplacement(int n, int inputSeq[]) {
    if (not valid (n, inputSeq))
        return 0;
    bool fix = false;
       int mn = 0;
    for (int i = 0; i < n; i++) {
        if (inputSeq[i] < inputSeq[mn])
            mn = i;
    }
    if (inputSeq[mn] <= n)
        rotate (inputSeq, inputSeq + (n + mn - inputSeq[mn] + 1) % n, inputSeq + n), fix = true;
    vector <int> rep;
    for (int i = 0; i < n; i++)
        if (inputSeq[i] > n)
            rep.push_back (inputSeq[i]);
    sort (rep.begin (), rep.end ());
    int sz = rep.size ();
    int lst = n, ans = 1;
    for (int i = 0; i < sz; i++) {
        ans = mult (ans, lgput (sz - i, rep[i] - lst - 1));
        lst = rep[i];
    }
    if (fix)
        return ans;
    return mult (ans, n);
}


#ifdef HOME
int gondolaSequence[100001];
int replacementSequence[250001];

int main()
{
  int i, n, tag;
  int nr;
  assert(scanf("%d", &tag)==1);
  assert(scanf("%d", &n)==1);
  for(i=0;i< n;i++)
    assert( scanf("%d", &gondolaSequence[i]) ==1);

  switch (tag){
  case 1: case 2: case 3:
    printf("%d\n", valid(n, gondolaSequence));
    break;

  case 4: case 5: case 6:
    nr = replacement(n, gondolaSequence, replacementSequence);
    printf("%d ", nr);
    if (nr > 0)
      {
	for (i=0; i<nr-1; i++)
	  printf("%d ", replacementSequence[i]);
	printf("%d\n", replacementSequence[nr-1]);
      }
    else printf("\n");
    break;

  case 7: case 8: case 9: case 10:
    printf("%d\n",  countReplacement(n, gondolaSequence));
    break;
  }

  return 0;
}
#endif // HOME
/**
8
14
6 94 8 9 10 93 12 13 95 1 2 3 4 5



**/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 15 ms 2124 KB Output is correct
7 Correct 11 ms 588 KB Output is correct
8 Correct 31 ms 3876 KB Output is correct
9 Correct 9 ms 1344 KB Output is correct
10 Correct 35 ms 4440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 15 ms 2112 KB Output is correct
7 Correct 14 ms 592 KB Output is correct
8 Correct 31 ms 3824 KB Output is correct
9 Correct 9 ms 1356 KB Output is correct
10 Correct 35 ms 4516 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 20 ms 2020 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 51 ms 4620 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Correct 1 ms 1228 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 2 ms 1228 KB Output is correct
11 Correct 11 ms 1508 KB Output is correct
12 Correct 12 ms 1644 KB Output is correct
13 Correct 14 ms 1612 KB Output is correct
14 Correct 11 ms 1484 KB Output is correct
15 Correct 23 ms 2112 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 50 ms 4392 KB Output is correct
10 Correct 38 ms 3652 KB Output is correct
11 Correct 14 ms 1484 KB Output is correct
12 Correct 17 ms 1868 KB Output is correct
13 Correct 4 ms 576 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 49 ms 4408 KB Output is correct
10 Correct 39 ms 3700 KB Output is correct
11 Correct 14 ms 1600 KB Output is correct
12 Correct 17 ms 1872 KB Output is correct
13 Correct 4 ms 572 KB Output is correct
14 Correct 60 ms 5340 KB Output is correct
15 Correct 69 ms 6020 KB Output is correct
16 Correct 11 ms 1288 KB Output is correct
17 Correct 45 ms 4108 KB Output is correct
18 Correct 24 ms 2380 KB Output is correct