oj.uz

답안 #95858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95858 2019-02-03T07:50:01 Z oolimry 자동 인형 (IOI18_doll) C++14
53 / 100
 808 ms 81576 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
std::set<int> sss;
void create_circuit(int M, std::vector<int> A) {
  int n = A.size();
  vector<int> C(M + 1);
  //C[0] = 1;
  //C[1] = -1;
  //C[2] = 1;
  //C[3] = 0;
  //C[4] = 0;
  int sw = 1000000;
  int xxx = 1;
  while(xxx < 1000000){
    sss.insert(xxx);
    xxx *= 2;
  }
  vector<int> X, Y;
 // X.push_back(2);
  //Y.push_back(3);

  vector<int> target[M+1];
  for(int i = 0;i < n-1;i++){
    target[A[i]].push_back(A[i+1]);
  }
  target[A[n-1]].push_back(0);
  target[0].push_back(A[0]);
  map<int, ii> mm;
  for(int i = 0;i <= M;i++){
    //printf("%d: ",i);


    if(target[i].size() == 0) C[i] = 0;
    else if(target[i].size() == 1) C[i] = target[i][0];
    else{

        int nn = *sss.lower_bound(target[i].size());
        int tree[2 * nn];
        tree[0] = 0;
        for(int j = nn;j < 2 * nn;j++){
            int l = j;
            int v = 0;
            while(l > 1){
                v *= 2;
                if(l % 2 == 1) v++;
                l /= 2;
            }
            tree[j] = v;
        }
        for(int j = 1;j < nn;j++){
            tree[j] = sw;
            sw++;
        }
        map<int,int> dis;
        for(int j = nn;j < 2 * nn;j++){
            if(j - nn < nn-target[i].size()) tree[j] = tree[1];
            else dis[tree[j]] = j;
            //else tree[j] = target[i][tree[j] - (nn - target[i].size())];
        }
        int c = 0;
        for(map<int,int>::iterator it = dis.begin();it != dis.end();it++){
            tree[it->second] = target[i][c];
            c++;
        }
        //for(int j = 0;j < 2 * nn;j++){
        //    printf("%d ",tree[j]);
        //}
        for(int j = 1;j < nn;j++){
            mm[tree[j]] = ii(tree[j*2],tree[j*2+1]);
        }
        C[i] = tree[1];
    }

    //printf("\n");
  }
  map<int,int> dis;
  for(map<int,ii>::iterator it = mm.begin();it != mm.end();it++){
    if(it->first >= 1000000) dis[it->first] = 0;
    if(it->second.first >= 1000000) dis[it->second.first] = 0;
    if(it->second.second >= 1000000) dis[it->second.second] = 0;
  }
  int c = -1;
  for(map<int,int>::iterator it = dis.begin();it != dis.end();it++){
        it->second = c;
        c--;
  }
  for(map<int,ii>::iterator it = mm.begin();it != mm.end();it++){
    if(it->first < 1000000) dis[it->first] = it->first;
    if(it->second.first < 1000000) dis[it->second.first] = it->second.first;
    if(it->second.second < 1000000) dis[it->second.second] = it->second.second;
  }
  map<int,ii> mmm;
  for(map<int,ii>::iterator it = mm.begin();it != mm.end();it++){
    mmm[dis[it->first]] = ii(dis[it->second.first],dis[it->second.second]);
  }
  for(map<int,ii>::iterator it = mmm.begin();it != mmm.end();it++){
    X.push_back(it->second.first);
    Y.push_back(it->second.second);
  }
  reverse(X.begin(),X.end());
  reverse(Y.begin(),Y.end());

  for(int i = 0;i < C.size();i++){
    if(C[i] >= 1000000) C[i] = dis[C[i]];
    //printf("%d ",C[i]);
  }
  /*
  printf("\n");
  for(int i = 0;i < X.size();i++){
    printf("%d %d\n",X[i],Y[i]);
  }
    */
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if(j - nn < nn-target[i].size()) tree[j] = tree[1];
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i = 0;i < C.size();i++){
      |                 ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 33 ms 6372 KB Output is correct
3 Correct 33 ms 5168 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 40 ms 7628 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 33 ms 6372 KB Output is correct
3 Correct 33 ms 5168 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 40 ms 7628 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 241 ms 21688 KB Output is correct
9 Correct 216 ms 19084 KB Output is correct
10 Correct 411 ms 32940 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 33 ms 6372 KB Output is correct
3 Correct 33 ms 5168 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 40 ms 7628 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 241 ms 21688 KB Output is correct
9 Correct 216 ms 19084 KB Output is correct
10 Correct 411 ms 32940 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 524 ms 48548 KB Output is correct
15 Correct 267 ms 24264 KB Output is correct
16 Correct 400 ms 36800 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 438 ms 40236 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 349 ms 28804 KB Output is correct
3 Partially correct 531 ms 55264 KB Output is partially correct
4 Partially correct 757 ms 56028 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 349 ms 28804 KB Output is correct
3 Partially correct 531 ms 55264 KB Output is partially correct
4 Partially correct 757 ms 56028 KB Output is partially correct
5 Partially correct 650 ms 62116 KB Output is partially correct
6 Partially correct 771 ms 70756 KB Output is partially correct
7 Partially correct 739 ms 67844 KB Output is partially correct
8 Partially correct 808 ms 76008 KB Output is partially correct
9 Partially correct 463 ms 55004 KB Output is partially correct
10 Partially correct 753 ms 79248 KB Output is partially correct
11 Partially correct 738 ms 81576 KB Output is partially correct
12 Partially correct 510 ms 53600 KB Output is partially correct
13 Partially correct 475 ms 46476 KB Output is partially correct
14 Partially correct 464 ms 44264 KB Output is partially correct
15 Partially correct 422 ms 40804 KB Output is partially correct
16 Partially correct 8 ms 1484 KB Output is partially correct
17 Partially correct 387 ms 41408 KB Output is partially correct
18 Partially correct 442 ms 41776 KB Output is partially correct
19 Partially correct 397 ms 44984 KB Output is partially correct
20 Partially correct 594 ms 56004 KB Output is partially correct
21 Partially correct 706 ms 70104 KB Output is partially correct
22 Partially correct 574 ms 53036 KB Output is partially correct