답안 #55251 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55251	2018-07-06T17:56:13 Z	Just_Solve_The_Problem	곤돌라 (IOI14_gondola)	C++11	100 / 100	29 ms	6268 KB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
//#include "grader.cpp"

using namespace std;

#define pb push_back
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define ll long long

const int N = (int)3e5 + 7;

int valid(int n, int inputSeq[]) {
  int cnt = 1, start = -1;
  for (int i = 0; i < n; i++) {
    if (inputSeq[i] == cnt) {
      start = i;
      break;
    }
  }
  for (int i = start; i < n; i++) {
    if (inputSeq[i] != cnt) {
      return 0;
    }
    cnt++;
  }
  for (int i = 0; i < start; i++) {
    if (inputSeq[i] != cnt) {
      return 0;
    }
    cnt++;
  }
  return 1;
}

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

int has[N], pos[N];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
  int start = -1, mx = -1;
  memset(pos, -1, sizeof pos);
  for (int i = 0; i < n; i++) {
    has[gondolaSeq[i]] = 1;
    pos[gondolaSeq[i]] = i;
    mx = max(mx, gondolaSeq[i]);
    if (gondolaSeq[i] <= n) {
      if (start != -1) continue;
      start = i - gondolaSeq[i] + 1;
      if (start < 0) start += n;
    }
  }
  deque < int > ans, dq;

  if (start == -1)
    start = 0;


  for (int i = n + 1; i <= mx; i++) {
    if (has[i]) {
      int qwe = pos[i];
      qwe -= start;
      if (qwe < 0) qwe += n;
      qwe++;
      ans.pb(qwe);
      while (!dq.empty()) {
        ans.pb(dq.front());
        dq.pop_front();
      }
      dq.clear();
    } else {
      dq.pb(i);
    }
  }

  int i = 0;
  for (int to : ans) {
    replacementSeq[i++] = to;
  }
  return i;
}

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

int mod = (int)1e9 + 9;

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

ll binpow(ll a, ll n) {
  ll res = 1;
  while (n) {
    if (n & 1) {
      res = mult(res, a);
    }
    a = mult(a, a);
    n >>= 1;
  }
  return res;
}

int countReplacement(int n, int inputSeq[]) {
  int res = 1;
  sort(inputSeq, inputSeq + n);
  for (int i = 0; i < n; i++) {
    if (inputSeq[i] <= n) continue;
    if (!i) {
      res = mult(res, binpow(n, inputSeq[i] - n - 1));
    } else {
      res = mult(res, binpow(n - i, inputSeq[i] - max(inputSeq[i - 1], n) - 1));
    }
  }
  if (inputSeq[0] > n) {
    res = mult(res, n);
  }
  return res;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	2 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	552 KB	Output is correct
2	Correct	3 ms	568 KB	Output is correct
3	Correct	2 ms	596 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	2 ms	596 KB	Output is correct
6	Correct	7 ms	748 KB	Output is correct
7	Correct	15 ms	1004 KB	Output is correct
8	Correct	10 ms	1004 KB	Output is correct
9	Correct	5 ms	1004 KB	Output is correct
10	Correct	15 ms	1004 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1004 KB	Output is correct
2	Correct	2 ms	1004 KB	Output is correct
3	Correct	3 ms	1004 KB	Output is correct
4	Correct	2 ms	1004 KB	Output is correct
5	Correct	3 ms	1004 KB	Output is correct
6	Correct	9 ms	1004 KB	Output is correct
7	Correct	14 ms	1004 KB	Output is correct
8	Correct	12 ms	1004 KB	Output is correct
9	Correct	5 ms	1004 KB	Output is correct
10	Correct	12 ms	1004 KB	Output is correct
11	Correct	2 ms	1004 KB	Output is correct
12	Correct	4 ms	1004 KB	Output is correct
13	Correct	9 ms	1004 KB	Output is correct
14	Correct	2 ms	1004 KB	Output is correct
15	Correct	18 ms	1004 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1788 KB	Output is correct
2	Correct	3 ms	1788 KB	Output is correct
3	Correct	4 ms	1788 KB	Output is correct
4	Correct	4 ms	1788 KB	Output is correct
5	Correct	3 ms	1788 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1792 KB	Output is correct
2	Correct	3 ms	1792 KB	Output is correct
3	Correct	4 ms	1792 KB	Output is correct
4	Correct	4 ms	1792 KB	Output is correct
5	Correct	4 ms	1792 KB	Output is correct
6	Correct	4 ms	1792 KB	Output is correct
7	Correct	3 ms	1792 KB	Output is correct
8	Correct	5 ms	1792 KB	Output is correct
9	Correct	4 ms	1792 KB	Output is correct
10	Correct	4 ms	1804 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1804 KB	Output is correct
2	Correct	4 ms	1804 KB	Output is correct
3	Correct	3 ms	1808 KB	Output is correct
4	Correct	4 ms	1808 KB	Output is correct
5	Correct	4 ms	1808 KB	Output is correct
6	Correct	4 ms	1808 KB	Output is correct
7	Correct	3 ms	1808 KB	Output is correct
8	Correct	4 ms	1808 KB	Output is correct
9	Correct	3 ms	1820 KB	Output is correct
10	Correct	4 ms	1864 KB	Output is correct
11	Correct	12 ms	2400 KB	Output is correct
12	Correct	16 ms	2476 KB	Output is correct
13	Correct	17 ms	3200 KB	Output is correct
14	Correct	14 ms	3200 KB	Output is correct
15	Correct	27 ms	4172 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4172 KB	Output is correct
2	Correct	2 ms	4172 KB	Output is correct
3	Correct	3 ms	4172 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4172 KB	Output is correct
2	Correct	3 ms	4172 KB	Output is correct
3	Correct	2 ms	4172 KB	Output is correct
4	Correct	2 ms	4172 KB	Output is correct
5	Correct	3 ms	4172 KB	Output is correct
6	Correct	3 ms	4172 KB	Output is correct
7	Correct	3 ms	4172 KB	Output is correct
8	Correct	3 ms	4172 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4172 KB	Output is correct
2	Correct	2 ms	4172 KB	Output is correct
3	Correct	2 ms	4172 KB	Output is correct
4	Correct	2 ms	4172 KB	Output is correct
5	Correct	2 ms	4172 KB	Output is correct
6	Correct	3 ms	4172 KB	Output is correct
7	Correct	2 ms	4172 KB	Output is correct
8	Correct	2 ms	4172 KB	Output is correct
9	Correct	20 ms	4172 KB	Output is correct
10	Correct	17 ms	4172 KB	Output is correct
11	Correct	9 ms	4172 KB	Output is correct
12	Correct	11 ms	4172 KB	Output is correct
13	Correct	5 ms	4172 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4172 KB	Output is correct
2	Correct	2 ms	4172 KB	Output is correct
3	Correct	2 ms	4172 KB	Output is correct
4	Correct	3 ms	4172 KB	Output is correct
5	Correct	2 ms	4172 KB	Output is correct
6	Correct	2 ms	4172 KB	Output is correct
7	Correct	2 ms	4172 KB	Output is correct
8	Correct	3 ms	4172 KB	Output is correct
9	Correct	29 ms	4172 KB	Output is correct
10	Correct	20 ms	4172 KB	Output is correct
11	Correct	9 ms	4172 KB	Output is correct
12	Correct	12 ms	4172 KB	Output is correct
13	Correct	5 ms	4172 KB	Output is correct
14	Correct	27 ms	4420 KB	Output is correct
15	Correct	29 ms	5500 KB	Output is correct
16	Correct	10 ms	5500 KB	Output is correct
17	Correct	22 ms	6016 KB	Output is correct
18	Correct	14 ms	6268 KB	Output is correct

답안 #55251

Compilation message