Submission #1177373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177373		emad234	Mechanical Doll (IOI18_doll)	C++20	0 / 100	20 ms	5680 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mod = 1e9 + 7;
const int mxN = 2e3 + 5;
const int mnN = 1e9 * -1;
using namespace std;
int curid = 0;
void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  int N = A.size();
  vector<int> X(N + 2), Y(N + 2), st(N + 3);
  vector<int> C(M + 1);
  int cur = 0;
  for(int i = 0;i <= M;i++) C[i] = -1e9;
  for(auto x : A){
    if(C[cur] == -1e9) C[cur] = x;
    else if(C[cur] < 0){
      int u = C[cur];
      while(1){
        st[-1 * u - 1] = !st[-1 * u - 1];
        if (st[-1 * u - 1])
        {
          if(X[-1 * u - 1] >= 0){
            curid++;
            X[curid - 1] = X[-1 * u - 1];
            Y[curid - 1] = x;
            X[-1 * u - 1] = -1 * curid;
            break;
          }else u = X[-1 * u - 1];
        }
        else
        {
          if (Y[-1 * u - 1] >= 0)
          {
            curid++;
            X[curid - 1] = Y[-1 * u - 1];
            Y[curid - 1] = x;
            Y[-1 * u - 1] = -1 * curid;
            break;
          }
          else u = Y[-1 * u - 1];
        }
      }
    }else{
      curid++;
      X[curid - 1] = C[cur];
      Y[curid - 1] = x;
      C[cur] = -1 * curid;
    }
    cur = x;
  }
  for(int i = 0;i <= M;i++){
    if(C[i] == -1e9) C[i] = 0;
    // cout<<C[i]<<' ';
  }
  // cout<<'\n';
  // for(int i = 1;i <= curid;i++){
  //   cout<<X[i - 1]<<' '<<Y[i - 1]<<'\n';
  // }
  answer(C, X, Y);
}

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