답안 #389157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389157	2021-04-13T18:16:57 Z	apostoldaniel854	곤돌라 (IOI14_gondola)	C++14	100 / 100	69 ms	6020 KB

gondola

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #389157

Compilation message