oj.uz

답안 #132702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132702 2019-07-19T11:14:15 Z dvdg6566 자동 인형 (IOI18_doll) C++14
26 / 100
 1000 ms 16628 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb emplace_back
#define SZ(x) (int)x.size()
 
inline int MSB(unsigned int x){
  return 32-__builtin_clz(x);
}
#define INF 1e9

vi occ[130100];
int c=-1;
vi X,Y;

void fill(int sizes, int numfill, int rt){
  // cout<<sizes<<' '<<numfill<<' '<<exit<<'\n';
  if (sizes == numfill){
    if (sizes == 2){
      X.pb(1);Y.pb(1);
      return;
    }
    int t=SZ(X);
    X.pb(c--);
    Y.pb(0);
    fill (sizes/2,numfill/2,rt);
    Y[t] = c--;
    fill(sizes/2,numfill/2,rt);
    return;
  }
  if (numfill == 2){
    if (sizes == 1){
      X.pb(rt);
      Y.pb(1);
    }else{
      X.pb(1);
      Y.pb(1);
    }
    return;
  }
  if (sizes*2 <= numfill){
    X.pb(rt);
    Y.pb(c--);
    fill (sizes, numfill/2,rt);
    return;
  }else{
    int t=SZ(X);
    X.pb(c--);
    Y.pb(0);
    fill (sizes-numfill/2, numfill/2, rt);
    Y[t] = c--;
    fill (numfill/2,numfill/2,rt);
    return;
  }
}

vi C;
int states[270100];

void simulate(int x){
  map<int,int> states;
  for (int t=0;t<SZ(occ[x]);++t){
    int cur=C[x];
    // cout<<"Simulate with dest "<<occ[x][t]<< " from "<<cur<<'\n';
    while (1){
      int nxt = X[-1-cur];
      if (states[-1-cur] == 1){
        nxt = Y[-1-cur];
      }
      // cout<<"At "<<cur<<" aka "<<-1-cur<<" next is "<<nxt<<'\n';
      if (nxt == 1){
        // cout<<"Change "<<-1-cur<<" when the state is "<<cur<<'\n';
        if (states[-1-cur] == 1){
          Y[-1-cur] = occ[x][t];
        }else{
          X[-1-cur] = occ[x][t];
        }
        states[-1-cur] = 1-states[-1-cur];
        break;
      }else{
        states[-1-cur] = 1-states[-1-cur];
        cur = nxt;
      }
    }
  }
}

void create_circuit(int M, std::vector<int> A) {
  int N = A.size();
  C.resize(M+1,-1);
  occ[0].pb(A[0]);
  for (int i=0;i<N-1;++i){
    occ[A[i]].pb(A[i+1]);
  }
  occ[A[N-1]].pb(0);
  for (int i=0;i<=M;++i){
    if (SZ(occ[i]) == 0){
      C[i]=0;
    }else if(SZ(occ[i]) == 1){
      C[i]=occ[i][0];
    }else if (SZ(occ[i]) == 2){
      C[i] = c;
      --c;
      X.pb(occ[i][0]);
      Y.pb(occ[i][1]);
    }else if (SZ(occ[i]) == 3){
      int a = c;
      C[i] = a;
      c -= 3;
      X.pb(a-1);
      Y.pb(a-2);
      X.pb(occ[i][0]);
      Y.pb(a);
      X.pb(occ[i][1]);
      Y.pb(occ[i][2]);
    }else if (SZ(occ[i]) == 4){
      int a = c;
      C[i] = a;
      c -= 3;
      X.pb(a-1);
      Y.pb(a-2);
      X.pb(occ[i][0]);
      Y.pb(occ[i][2]);
      X.pb(occ[i][1]);
      Y.pb(occ[i][3]);
    }else{
      int N = SZ(occ[i]);
      int t = MSB(N-1);
      int l = (1<<t);
      int cc=c;
      C[i] = c--;
      fill(N,l,cc);
    }
    // cout<<"Value "<<i<<" ends at "<<c<<'\n';
    // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
  }
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<"\n\n";
  // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
  for (int i=0;i<=M;++i){
    if (SZ(occ[i]) > 4)simulate(i);
  }
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<"\n\n";
  // for (int i=0;i<SZ(X);++i)cout<<X[i]<<' '<<Y[i]<<'\n';
  // for (int i=0;i<=M;++i)cout<<C[i]<<' ';cout<<'\n';
  answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 31 ms 6988 KB Output is correct
3 Correct 28 ms 6696 KB Output is correct
4 Correct 3 ms 3276 KB Output is correct
5 Correct 15 ms 4428 KB Output is correct
6 Correct 59 ms 8396 KB Output is correct
7 Correct 4 ms 3276 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 31 ms 6988 KB Output is correct
3 Correct 28 ms 6696 KB Output is correct
4 Correct 3 ms 3276 KB Output is correct
5 Correct 15 ms 4428 KB Output is correct
6 Correct 59 ms 8396 KB Output is correct
7 Correct 4 ms 3276 KB Output is correct
8 Correct 55 ms 8884 KB Output is correct
9 Correct 71 ms 9344 KB Output is correct
10 Correct 87 ms 11676 KB Output is correct
11 Correct 4 ms 3336 KB Output is correct
12 Correct 3 ms 3276 KB Output is correct
13 Correct 3 ms 3276 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 31 ms 6988 KB Output is correct
3 Correct 28 ms 6696 KB Output is correct
4 Correct 3 ms 3276 KB Output is correct
5 Correct 15 ms 4428 KB Output is correct
6 Correct 59 ms 8396 KB Output is correct
7 Correct 4 ms 3276 KB Output is correct
8 Correct 55 ms 8884 KB Output is correct
9 Correct 71 ms 9344 KB Output is correct
10 Correct 87 ms 11676 KB Output is correct
11 Correct 4 ms 3336 KB Output is correct
12 Correct 3 ms 3276 KB Output is correct
13 Correct 3 ms 3276 KB Output is correct
14 Correct 110 ms 13300 KB Output is correct
15 Correct 54 ms 8236 KB Output is correct
16 Correct 90 ms 10888 KB Output is correct
17 Correct 3 ms 3276 KB Output is correct
18 Correct 4 ms 3276 KB Output is correct
19 Correct 4 ms 3276 KB Output is correct
20 Correct 96 ms 12392 KB Output is correct
21 Correct 3 ms 3276 KB Output is correct
22 Correct 4 ms 3276 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 747 ms 12724 KB Output is correct
3 Correct 729 ms 12724 KB Output is correct
4 Execution timed out 1087 ms 16628 KB Time limit exceeded

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 747 ms 12724 KB Output is correct
3 Correct 729 ms 12724 KB Output is correct
4 Execution timed out 1087 ms 16628 KB Time limit exceeded