oj.uz

답안 #147623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147623 2019-08-30T10:17:38 Z Bodo171 자동 인형 (IOI18_doll) C++14
100 / 100
 123 ms 15520 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=800005;
vector<int> C,X,Y,a,act;
int et[nmax],lf[nmax],rg[nmax],w[nmax],rly[nmax];
int p,u,ets,i,lg,reale;
void build(int nod,int l,int r)
{
    if(l==r)
    {
        w[nod]=(act[l]!=(1<<30));
        rly[nod]=act[l];
        return;
    }
    int m=(l+r)/2;
    build(2*nod,l,m);
    build(2*nod+1,m+1,r);
    w[nod]=w[2*nod]+w[2*nod+1];
    if(w[nod]>0)
    {
        ++reale;
        rly[nod]=-reale;
        X.push_back(rly[2*nod]);
        Y.push_back(rly[2*nod+1]);
    }
    else rly[nod]=(1<<30);
}
int rev(int x,int lg)
{
    int ret=0;
    for(int b=0;b<lg;b++)
    {
        if((x&(1<<b)))
            ret|=(1<<(lg-b-1));
    }
    return ret;
}
void create_circuit(int M, std::vector<int> A) {
  int n = A.size();
  A.push_back(0);
  C.resize(M+1);
  for(i=0;i<=M;i++)
    C[i]=-1;
  while((1<<lg)<n+1)
    lg++;
  act.resize((1<<lg),(1<<30));
  int cat=0;
  for(i=0;i<(1<<lg);i++)
    {
        if(rev(i,lg)>=(1<<lg)-n-1)
         act[rev(i,lg)]=A[cat++];
    }
  build(1,0,(1<<lg)-1);
  for(i=0;i<=M;i++)
    C[i]=rly[1];
  for(i=0;i<X.size();i++)
  {
    if(X[i]==(1<<30)) X[i]=rly[1];
    if(Y[i]==(1<<30)) Y[i]=rly[1];
  }
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:57:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(i=0;i<X.size();i++)
      |           ~^~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 7200 KB Output is correct
3 Correct 41 ms 6972 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 62 ms 8904 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 7200 KB Output is correct
3 Correct 41 ms 6972 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 62 ms 8904 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 94 ms 11988 KB Output is correct
9 Correct 97 ms 12628 KB Output is correct
10 Correct 116 ms 15520 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 7200 KB Output is correct
3 Correct 41 ms 6972 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 62 ms 8904 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 94 ms 11988 KB Output is correct
9 Correct 97 ms 12628 KB Output is correct
10 Correct 116 ms 15520 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 103 ms 14916 KB Output is correct
15 Correct 79 ms 11360 KB Output is correct
16 Correct 99 ms 14468 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 123 ms 15156 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 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 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 65 ms 10216 KB Output is correct
3 Correct 67 ms 10216 KB Output is correct
4 Correct 93 ms 12880 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 65 ms 10216 KB Output is correct
3 Correct 67 ms 10216 KB Output is correct
4 Correct 93 ms 12880 KB Output is correct
5 Correct 101 ms 14364 KB Output is correct
6 Correct 99 ms 13852 KB Output is correct
7 Correct 94 ms 13988 KB Output is correct
8 Correct 94 ms 13584 KB Output is correct
9 Correct 67 ms 10212 KB Output is correct
10 Correct 111 ms 13472 KB Output is correct
11 Correct 96 ms 13092 KB Output is correct
12 Correct 67 ms 10452 KB Output is correct
13 Correct 73 ms 10916 KB Output is correct
14 Correct 69 ms 10956 KB Output is correct
15 Correct 71 ms 11136 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 72 ms 8244 KB Output is correct
18 Correct 70 ms 10448 KB Output is correct
19 Correct 97 ms 10384 KB Output is correct
20 Correct 95 ms 13340 KB Output is correct
21 Correct 90 ms 13152 KB Output is correct
22 Correct 108 ms 13180 KB Output is correct