oj.uz

답안 #974647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
974647 2024-05-03T14:59:10 Z hariaakas646 곤돌라 (IOI14_gondola) C++14
90 / 100
 1000 ms 5360 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;

int valid(int n, int inputSeq[])
{
  pii mi = mp(2e9, 1e9);
  seti st;
  frange(i, n) {
    mi = min(mi, mp(inputSeq[i], i));
    st.insert(inputSeq[i]);
  }
  if(st.size() != n) return 0;
  if(mi.f > n) return 1;
  int v = mi.f;
  forr(i, mi.s, n) {
    if(inputSeq[i] <= n) {
      if(inputSeq[i] != v) return 0;
    }
    v++;
  }
  forr(i, 0, mi.s) {
    if(inputSeq[i] <= n) {
      if(inputSeq[i] != v) return 0;
    }
    v++;
  }
  return 1;
}

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

int replacement(int n, int inputSeq[], int replacementSeq[])
{
  pii mi = mp(2e9, 1e9);
  int ma = 0;
  vi pos(3e5+1, -1);
  frange(i, n) {
    mi = min(mi, mp(inputSeq[i], i));
    ma = max(ma, inputSeq[i]);
    pos[inputSeq[i]] = i;
  }
  
  if(mi.f > n) {
    int v = pos[ma]+1;
    pos[ma] = -1;
    forr(i, n+1, ma+1) {
      if(pos[i] == -1) {
        replacementSeq[i-(n+1)] = v;
        v = i;
      }
      else {
        replacementSeq[i-(n+1)] = pos[i]+1;
      }
    }
  }
  else {
    vi val(n);
    int v1 = mi.f;
    frange(i, n) {
      val[i] = ((v1-1) + (i-mi.s) + n) % n + 1; 
      // printf("%d ", val[i]);
    }

    int v = val[pos[ma]];
    pos[ma] = -1;
    forr(i, n+1, ma+1) {
      // printf("%d\n", i);
      if(pos[i] == -1) {
        // printf("%d\n", v);
        replacementSeq[i-(n+1)] = v;
        v = i;
      }
      else {

        replacementSeq[i-(n+1)] = val[pos[i]];
      }
    }

  }
  return ma-n;
}

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

int countReplacement(int n, int inputSeq[])
{
  const lli mod = 1e9 + 9;
  if(!valid(n, inputSeq)) return 0;
  lli out = 1;
  int ma = 0;
  int mi = 2e9;
  int c = n;
  seti st;
  frange(i, n) {ma = max(ma, inputSeq[i]); st.insert(inputSeq[i]);}
  mi = *st.begin();
  if(mi > n) {
    out = n;
  }
  frange(i, n) {
    if(inputSeq[i] <= n) c--;
  }
  forr(i, n+1, ma+1) {
    if(st.find(i) == st.end()) {
      out = (out * c) %mod;
    }
    else {
      c--;
    }
  }
  return out;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:36:16: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |   if(st.size() != n) return 0;
      |      ~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 2484 KB Output is correct
7 Correct 21 ms 4176 KB Output is correct
8 Correct 19 ms 4444 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 20 ms 4952 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 21 ms 4300 KB Output is correct
8 Correct 16 ms 4444 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 19 ms 4956 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 448 KB Output is correct
13 Correct 10 ms 2396 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 28 ms 5212 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 8 ms 2628 KB Output is correct
12 Correct 11 ms 2648 KB Output is correct
13 Correct 10 ms 2140 KB Output is correct
14 Correct 8 ms 2652 KB Output is correct
15 Correct 15 ms 2392 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 41 ms 4632 KB Output is correct
10 Correct 32 ms 3928 KB Output is correct
11 Correct 14 ms 1628 KB Output is correct
12 Correct 15 ms 1884 KB Output is correct
13 Correct 6 ms 604 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 41 ms 4572 KB Output is correct
10 Correct 32 ms 3876 KB Output is correct
11 Correct 14 ms 1624 KB Output is correct
12 Correct 15 ms 1884 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Execution timed out 1090 ms 5360 KB Time limit exceeded
15 Halted 0 ms 0 KB -