oj.uz

Submission #114244

# Submission time Handle Problem Language Result Execution time Memory
114244 2019-05-31T14:47:24 Z faustaadp Mechanical Doll (IOI18_doll) C++17
100 / 100
 146 ms 16268 KB 
#include "doll.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,te,ki[404040],ka[404040],con[404040],i,N;
vector<ll> isi;
ll cak(ll aa)
{
  ll ii;
  for(ii=0;ii<30;ii++)
  {
    if((1<<ii)>=aa)
      return (1<<ii);
  }
  return 0;
}
ll buat(ll aa,ll bb,ll cc,ll dd)
{
  if(bb==1)
  {
    isi.pb(cc);
    return -cc;
  }
  if(aa==0)
    return 1;
  else
  {
    te++;
    ll tem=te;
    ll x=min(bb/2,aa);
    ki[tem]=-buat(aa-x,bb/2,cc,dd*2);
    ka[tem]=-buat(x,bb/2,cc+dd,dd*2);
    return tem;
  }
}     
void create_circuit(int M, std::vector<int> A) 
{
  n=A.size();
  m=M;
  std::vector<int> C(M + 1);
  N=cak(n+1);
 // cout<<N<<"\n";
  C[0]=-buat(n+1,N,0,1);
  for(i=1;i<=m;i++)
    C[i]=-1;
  sort(isi.begin(),isi.end());
  for(i=n+1;i<(ll)isi.size();i++)
    A.pb(-1);
  A.pb(0);  
  for(i=0;i<(ll)isi.size();i++)
  {
    //cout<<isi[i]<<" _ "<<i<<"\n";
    con[isi[i]]=i;
  }
  for(i=1;i<=te;i++)
  {
    if(ki[i]>=0)
      ki[i]=A[con[ki[i]]];
    if(ka[i]>=0)
      ka[i]=A[con[ka[i]]];
  }
  std::vector<int> X(te);
  std::vector<int> Y(te);
  for(i=1;i<=te;i++)
  {
    //cout<<i<<" "<<ki[i]<<" "<<ka[i]<<"\n";
    X[i-1]=ki[i];
    Y[i-1]=ka[i];
  }
  answer(C, X, Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 43 ms 6812 KB Output is correct
3 Correct 39 ms 6428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 60 ms 8772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 43 ms 6812 KB Output is correct
3 Correct 39 ms 6428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 60 ms 8772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 69 ms 11856 KB Output is correct
9 Correct 70 ms 12324 KB Output is correct
10 Correct 134 ms 16268 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 43 ms 6812 KB Output is correct
3 Correct 39 ms 6428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 60 ms 8772 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 69 ms 11856 KB Output is correct
9 Correct 70 ms 12324 KB Output is correct
10 Correct 134 ms 16268 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 146 ms 15876 KB Output is correct
15 Correct 67 ms 11496 KB Output is correct
16 Correct 102 ms 15716 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 105 ms 16080 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 68 ms 10768 KB Output is correct
3 Correct 60 ms 10708 KB Output is correct
4 Correct 94 ms 14416 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 68 ms 10768 KB Output is correct
3 Correct 60 ms 10708 KB Output is correct
4 Correct 94 ms 14416 KB Output is correct
5 Correct 103 ms 15600 KB Output is correct
6 Correct 101 ms 15464 KB Output is correct
7 Correct 146 ms 15680 KB Output is correct
8 Correct 101 ms 15112 KB Output is correct
9 Correct 62 ms 10660 KB Output is correct
10 Correct 96 ms 15124 KB Output is correct
11 Correct 93 ms 14688 KB Output is correct
12 Correct 59 ms 10916 KB Output is correct
13 Correct 63 ms 11312 KB Output is correct
14 Correct 87 ms 11376 KB Output is correct
15 Correct 64 ms 11512 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 59 ms 9464 KB Output is correct
18 Correct 61 ms 10968 KB Output is correct
19 Correct 63 ms 10892 KB Output is correct
20 Correct 101 ms 14992 KB Output is correct
21 Correct 105 ms 14728 KB Output is correct
22 Correct 101 ms 14740 KB Output is correct