답안 #55242 :: oj.uz

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

gondola

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

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[]) {
  if (!valid(n, inputSeq)) return 0;
  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	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	408 KB	Output is correct
4	Correct	3 ms	408 KB	Output is correct
5	Correct	2 ms	524 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	524 KB	Output is correct
2	Correct	3 ms	532 KB	Output is correct
3	Correct	2 ms	696 KB	Output is correct
4	Correct	2 ms	732 KB	Output is correct
5	Correct	2 ms	772 KB	Output is correct
6	Correct	8 ms	1056 KB	Output is correct
7	Correct	13 ms	1692 KB	Output is correct
8	Correct	11 ms	2084 KB	Output is correct
9	Correct	6 ms	2084 KB	Output is correct
10	Correct	49 ms	2820 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2820 KB	Output is correct
2	Correct	2 ms	2820 KB	Output is correct
3	Correct	2 ms	2820 KB	Output is correct
4	Correct	3 ms	2820 KB	Output is correct
5	Correct	2 ms	2820 KB	Output is correct
6	Correct	20 ms	2824 KB	Output is correct
7	Correct	17 ms	3536 KB	Output is correct
8	Correct	13 ms	3936 KB	Output is correct
9	Correct	6 ms	3936 KB	Output is correct
10	Correct	17 ms	4576 KB	Output is correct
11	Correct	2 ms	4576 KB	Output is correct
12	Correct	3 ms	4576 KB	Output is correct
13	Correct	10 ms	4576 KB	Output is correct
14	Correct	3 ms	4576 KB	Output is correct
15	Correct	17 ms	5320 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6212 KB	Output is correct
2	Correct	3 ms	6216 KB	Output is correct
3	Correct	4 ms	6220 KB	Output is correct
4	Correct	3 ms	6224 KB	Output is correct
5	Correct	3 ms	6228 KB	Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6412 KB	Output is correct
2	Correct	4 ms	6420 KB	Output is correct
3	Correct	4 ms	6420 KB	Output is correct
4	Correct	4 ms	6420 KB	Output is correct
5	Correct	3 ms	6432 KB	Output is correct
6	Correct	3 ms	6436 KB	Output is correct
7	Correct	4 ms	6440 KB	Output is correct
8	Correct	23 ms	6448 KB	Output is correct
9	Correct	5 ms	6452 KB	Output is correct
10	Correct	4 ms	6452 KB	Output is correct
11	Correct	16 ms	7480 KB	Output is correct
12	Correct	20 ms	8060 KB	Output is correct
13	Correct	32 ms	8916 KB	Output is correct
14	Correct	14 ms	8916 KB	Output is correct
15	Correct	26 ms	10600 KB	Output is correct

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	10600 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	10600 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	10600 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	10600 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

답안 #55242

Compilation message