Submission #283982

#	Time	Username	Problem	Language	Result	Execution time	Memory
283982		milleniumEeee	Mechanical Doll (IOI18_doll)	C++14	2 / 100	57 ms	5136 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;
 
int N, M, S;
vector <int> A, C, X, Y;
 
struct Solve_for_permutaion {
  bool need() {
    vector <int> cnt((int)4e5 + 5, 0);
    bool ok = 1;
    for (int i = 1; i <= N; i++) {
      cnt[A[i]]++;
    }
    for (int i = 1; i <= M; i++) {
      ok &= (cnt[i] <= 1);
    }
    return ok;
  }
  void solve() {
    for (int i = 1; i <= N; i++) {
      C[A[i - 1]] = A[i];
    }
    C[A[N]] = 0;
  }
}subtask1;
 
struct Solve_for_two {
  vector <int> cnt;
  Solve_for_two() {
    cnt.resize((int)1e5 + 5, 0);
  }
  bool need() {
    bool ok = 1;
    for (int i = 1; i <= N; i++) {
      cnt[A[i]]++;
    }
    for (int i = 1; i <= M; i++) {
      ok &= (cnt[i] <= 2);
    }
    return ok;
  }
  
  struct Para {
    int trigger, switcher;
    Para (int trigger_, int switcher_) {
      trigger = trigger_;      
      switcher = switcher_;
    }
    Para () {
      trigger = -1;      
      switcher = -1;
    }
  };

  void solve() {
    vector <int> pos(M + 5, 0);
    vector <pii> twice(M + 5, {-1, -1});
    for (int i = 1; i <= N; i++) {
      pos[A[i]] = i;
      if (!pos[A[i]]) {
        twice[A[i]].fr = i;
      } else {
        twice[A[i]].sc = i;
      }
    }
    int id = -1;
    int siz = 0;
    C[0] = A[1];
    vector <Para> vec;
    for (int i = 1; i <= M; i++) {
      if (cnt[i] == 0) {
        continue;
      }
      if (cnt[i] == 1) {
        int nxt = (pos[A[i]] < N ? A[pos[A[i]] + 1] : 0);
        C[A[i]] = nxt;
      }
      if (cnt[i] == 2) {
        C[A[i]] = id--, siz++;
        vec.push_back(Para(i, C[A[i]]));// our trigger and his switcher
      }
    }
    X.resize(siz);
    Y.resize(siz);
    for (auto el : vec) {
      int id = (-el.switcher) - 1;
      X[id] = A[twice[el.trigger].fr + 1];
      if (twice[el.trigger].sc == N) {
        Y[id] = 0;
      } else {
        Y[id] = A[twice[el.trigger].sc + 1];
      }
    }
  }
}subtask2;
 
// A - sequance 
// C - edges of triggers
// X/Y - edges of switches
// M - triggers vertexes
 
void create_circuit(int MM, vector<int> AA) {
  M = MM;
  N = AA.size();
  A.resize(N + 1);
  A[0] = 0;
  for (int i = 0; i < N; i++) {
    A[i + 1] = AA[i];
  }
  C.resize(M + 1);
  if (subtask1.need()) {
    subtask1.solve();
  }
  else if (subtask2.need()) {
    subtask2.solve();
  }
  answer(C, X, Y);
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56