oj.uz

Submission #784803

# Submission time Handle Problem Language Result Execution time Memory
784803 2023-07-16T14:39:34 Z QwertyPi Mechanical Doll (IOI18_doll) C++14
10 / 100
 1000 ms 20680 KB 
#include "doll.h"
#include <bits/stdc++.h>

const int SLOT = 1234567;
using namespace std; 

int S = 0;
map<int, int> MX, MY; 
map<int, bool> T;
int build(int lv, int n){
	if(n == 0) return 0;
	if(lv == 0) return SLOT;
	int sr = min(n, 1 << lv - 1), sl = n - sr; 
	int vl = build(lv - 1, sl);
	int vr = build(lv - 1, sr);
	int v = --S;
	MX[v] = vl, MY[v] = vr;
	return v;
}

void create_circuit(int M, vector<int> A) {
  A.push_back(0);
  int N = A.size();
  std::vector<int> C(M + 1);
  int level = 0; int x = N; while(x > (1 << level)) level++;
  build(level, N);
  int root = S;
  C[0] = root;
  for (int i = 1; i <= M; ++i) {
    C[i] = root;
  }
  for(auto& [a, b] : MX) if(b == 0) b = root;
  for(auto& [a, b] : MY) if(b == 0) b = root;
  for(auto i : MX) T[i.first] = 0;
  int cur = 0, filled = 0;
  while(filled < N){
  	if(cur >= 0) cur = C[cur];
	  else {
  		if(T[cur] && MY[cur] == SLOT) MY[cur] = A[filled++];
  		if(!T[cur] && MX[cur] == SLOT) MX[cur] = A[filled++];
  		int nxt = T[cur] ? MY[cur] : MX[cur]; T[cur] ^= 1;
  		cur = nxt;
	}
  }
  
  std::vector<int> X(MX.size()), Y(MY.size());
  for (int k = 0; k < MX.size(); ++k) {
  	X[k] = MX[-k - 1], Y[k] = MY[-k - 1];
  }
  answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int build(int, int)':
doll.cpp:13:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   13 |  int sr = min(n, 1 << lv - 1), sl = n - sr;
      |                       ~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:32:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |   for(auto& [a, b] : MX) if(b == 0) b = root;
      |             ^
doll.cpp:33:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |   for(auto& [a, b] : MY) if(b == 0) b = root;
      |             ^
doll.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int k = 0; k < MX.size(); ++k) {
      |                   ~~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 722 ms 13688 KB Output is correct
3 Correct 703 ms 13824 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Execution timed out 1081 ms 16236 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 722 ms 13688 KB Output is correct
3 Correct 703 ms 13824 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Execution timed out 1081 ms 16236 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 722 ms 13688 KB Output is correct
3 Correct 703 ms 13824 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 8 ms 1492 KB Output is correct
6 Execution timed out 1081 ms 16236 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1060 ms 20680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1060 ms 20680 KB Time limit exceeded
3 Halted 0 ms 0 KB -