제출 #422764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422764		fedoseevtimofey	곤돌라 (IOI14_gondola)	C++14	75 / 100	46 ms	5256 KiB

gondola

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
 
using namespace std;
 
typedef long long ll;

#include "gondola.h"

int valid(int n, int inputSeq[])
{
  if (n == 1) return true;
  vector <int> a(n);
  set <int> diff;
  bool big = true;
  for (int i = 0; i < n; ++i) {
    a[i] = inputSeq[i];
    big &= (a[i] > n);
    diff.insert(a[i]);
  }
  if ((int)diff.size() != n) return 0; 
  if (big) return true;
  vector <int> nums(n, -1);
  for (int i = 0; i < n; ++i) {
    if (a[i] <= n) {
      nums[i] = a[i] - 1;
    }
  }
  for (int it = 0; it < 2; ++it) {
    for (int i = 0; i < n; ++i) {
      if (nums[i] == -1) continue;
      int j = (i + 1) % n;
      if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
      if (nums[j] != (nums[i] + 1) % n) {
        return false;
      }
    }
  }
  return true;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = gondolaSeq[i];
    --a[i];
  }
  vector <int> nums(n, -1);
  for (int i = 0; i < n; ++i) {
    if (a[i] < n) {
      nums[i] = a[i];
    }
  }
  for (int it = 0; it < 2; ++it) {
    for (int i = 0; i < n; ++i) {
      if (nums[i] == -1) continue;
      int j = (i + 1) % n;
      if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
      if (nums[j] != (nums[i] + 1) % n) {
        assert(false);
      }
    }
  }
  for (int i = 0; i < n; ++i) if (nums[i] == -1) nums[i] = i; 
  vector <int> p(n);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&] (int i, int j) {
    return a[i] < a[j];
  });
  int x = n;
  int uk = 0;
  auto add = [&] (int x) {
    replacementSeq[uk++] = x + 1;
  };
  for (int i : p) {
    while (nums[i] != a[i]) {
      add(nums[i]);
      nums[i] = x++;
    }
  }
  return uk;
}     

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

const int md = 1e9 + 9;

int mul(int a, int b) {
  return ((ll)a * b) % md;
}

int power(int a, ll b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

int countReplacement(int n, int inputSeq[])
{
  if (!valid(n, inputSeq)) return 0;
  vector <int> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = inputSeq[i];
    --a[i];
  }
  vector <int> nums(n, -1);
  for (int i = 0; i < n; ++i) {
    if (a[i] < n) {
      nums[i] = a[i];
    }
  }
  for (int it = 0; it < 2; ++it) {
    for (int i = 0; i < n; ++i) {
      if (nums[i] == -1) continue;
      int j = (i + 1) % n;
      if (nums[j] == -1) nums[j] = (nums[i] + 1) % n;
      if (nums[j] != (nums[i] + 1) % n) {
        assert(false);
      }
    }
  }
  vector <int> intr;
  for (int i = 0; i < n; ++i) {
    if (a[i] != nums[i]) {
      intr.push_back(a[i]);
    }
  }
  sort(intr.begin(), intr.end());
  int ans = 1;
  int lst = n;
  for (int i = 0; i < (int)intr.size(); ++i) {
    int cnt = intr[i] - lst;
    ans = mul(ans, power((int)intr.size() - i, cnt));
    lst = intr[i] + 1;
  }   
  if (nums[0] == -1) {
    for (int i = 1; i <= n; ++i) ans = mul(ans, i);
  } 
  return ans;
}
 
#ifdef LOCAL
int gondolaSequence[100001];
int replacementSequence[250001];
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int i, n, tag;
  int nr; 
  cin >> tag;
  cin >> n;
  for(i=0;i< n;i++)
    cin >> gondolaSequence[i];
  
  switch (tag){
  case 1: case 2: case 3:
    cout << valid(n, gondolaSequence) << '\n';
    break;

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

  case 7: case 8: case 9: case 10:
    cout << countReplacement(n, gondolaSequence) << '\n';
    break;
  }

  return 0;
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10