Submission #95859

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
95859	2019-02-03T07:55:17 Z	oolimry	Mechanical Doll (IOI18_doll)	C++14	16 / 100	637 ms	48544 KB

doll

#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 = nn-1;j >= 1;j--){
            if(tree[j*2] == tree[j*2+1]) tree[j] = tree[j*2];
        }
        for(int j = 1;j < nn;j++){
            if(tree[j] < 1000000) continue;
            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:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int i = 0;i < C.size();i++){
      |                 ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	204 KB	Output is correct
2	Correct	34 ms	6348 KB	Output is correct
3	Correct	28 ms	5116 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	14 ms	3808 KB	Output is correct
6	Correct	44 ms	7620 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	2 ms	204 KB	Output is correct
2	Correct	34 ms	6348 KB	Output is correct
3	Correct	28 ms	5116 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	14 ms	3808 KB	Output is correct
6	Correct	44 ms	7620 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	245 ms	21704 KB	Output is correct
9	Correct	171 ms	19196 KB	Output is correct
10	Correct	362 ms	32932 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	2 ms	204 KB	Output is correct
2	Correct	34 ms	6348 KB	Output is correct
3	Correct	28 ms	5116 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	14 ms	3808 KB	Output is correct
6	Correct	44 ms	7620 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	245 ms	21704 KB	Output is correct
9	Correct	171 ms	19196 KB	Output is correct
10	Correct	362 ms	32932 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	637 ms	48544 KB	Output is correct
15	Correct	274 ms	24224 KB	Output is correct
16	Correct	421 ms	36896 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	441 ms	40220 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct