Submission #946677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
946677	2024-03-14T22:03:39 Z	PagodePaiva	Mechanical Doll (IOI18_doll)	C++17	16 / 100	74 ms	16728 KB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define M 100010
using namespace std;

vector <int> g[M];
int c[2*M], x[2*M], y[2*M];
int tp = 1;

void solve(int val, vector <int> &v){
  tp = max(tp, val);
  if(v.size() == 2){
    x[val] = v[0];
    y[val] = v[1];
    return;
  }
  vector <int> a, b;
  for(int i = 0;i < v.size();i++){
    if(!(i % 2)) a.push_back(v[i]);
    else b.push_back(v[i]);
  }
  if(a.size() % 2 != b.size() % 2){
    int t = a.back();
    a.pop_back();
    b.push_back(t);
    a.push_back(-val);
  }
  x[val] = -(val+1);
  solve(val+1, a);
  y[val] = -(tp+1);
  solve(tp+1, b);
  return;
}

void create_circuit(int m, std::vector<int> A) {
  vector <int> a;
  a.push_back(0);
  for(auto x : A) a.push_back(x);
  a.push_back(0);
  for(int i = 0;i < (int) (a.size())-1;i++){
    g[a[i]].push_back(a[i+1]);
  }
  for(int i = 0;i <= m;i++){
    if(g[i].size() == 0){
      c[i] = 0;
      continue;
    }
    if(g[i].size() == 1){
      c[i] = g[i][0];
      continue;
    }
    c[i] = -tp;
    solve(tp, g[i]);
    tp++;
  }
  vector <int> cc, xx, yy;
  for(int i = 0;i <= m;i++) cc.push_back(c[i]);
  for(int i = 1;i < tp;i++){
    xx.push_back(x[i]);
    yy.push_back(y[i]);
  }
  // for(auto t : cc) cout << t << ' ';
  //   cout << endl;
  // for(int i = 0;i < xx.size();i++){
  //   cout << xx[i] << ' ' << yy[i] << endl;
  // }
  answer(cc, xx, yy);
  return;
}

Compilation message

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

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4956 KB	Output is correct
2	Correct	18 ms	9536 KB	Output is correct
3	Correct	15 ms	8916 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	8 ms	6100 KB	Output is correct
6	Correct	22 ms	11096 KB	Output is correct
7	Correct	1 ms	4952 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4956 KB	Output is correct
2	Correct	18 ms	9536 KB	Output is correct
3	Correct	15 ms	8916 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	8 ms	6100 KB	Output is correct
6	Correct	22 ms	11096 KB	Output is correct
7	Correct	1 ms	4952 KB	Output is correct
8	Correct	36 ms	12300 KB	Output is correct
9	Correct	35 ms	12740 KB	Output is correct
10	Correct	51 ms	16040 KB	Output is correct
11	Correct	1 ms	4952 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	1 ms	4956 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4956 KB	Output is correct
2	Correct	18 ms	9536 KB	Output is correct
3	Correct	15 ms	8916 KB	Output is correct
4	Correct	1 ms	4956 KB	Output is correct
5	Correct	8 ms	6100 KB	Output is correct
6	Correct	22 ms	11096 KB	Output is correct
7	Correct	1 ms	4952 KB	Output is correct
8	Correct	36 ms	12300 KB	Output is correct
9	Correct	35 ms	12740 KB	Output is correct
10	Correct	51 ms	16040 KB	Output is correct
11	Correct	1 ms	4952 KB	Output is correct
12	Correct	1 ms	4956 KB	Output is correct
13	Correct	1 ms	4956 KB	Output is correct
14	Correct	66 ms	16728 KB	Output is correct
15	Correct	39 ms	11920 KB	Output is correct
16	Correct	60 ms	14936 KB	Output is correct
17	Correct	1 ms	4956 KB	Output is correct
18	Correct	1 ms	4956 KB	Output is correct
19	Correct	2 ms	4956 KB	Output is correct
20	Correct	60 ms	16096 KB	Output is correct
21	Correct	1 ms	4956 KB	Output is correct
22	Correct	1 ms	4956 KB	Output is correct