oj.uz

Submission #944817

# Submission time Handle Problem Language Result Execution time Memory
944817 2024-03-13T06:05:35 Z PenguinsAreCute Mechanical Doll (IOI18_doll) C++17
100 / 100
 82 ms 13824 KB 
// why is there always this nvim thing where all numbers increase by 1 if you accidentally press sth
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define pb emplace_back
int rev(int bits, int n) {
	int ans = 0;
	REP(i,0,bits) if(n&(1<<i)) ans |= (1<<(bits-1-i));
	return ans;
}
#ifdef DEBUG
	#define state printf
	#define RTEfind printf("Line %d\n",__LINE__)
#else
	#define state(...) 69
	#define RTEfind 42
#endif
void create_circuit(int M, std::vector<int> A) {
	state("create circuit called\n");
	A.pb(0);
	RTEfind;
	int N = A.size();
	RTEfind;
	vector<int> C;
	RTEfind;
	REP(i,0,M+1) C.pb(-1);
	RTEfind;
	int log = 0; while((1<<log)<N) log++;
	RTEfind;
	int no[(2<<log)];
	RTEfind;
	REP(i,1<<log,2<<log) no[i]=-(i+N<(2<<log));
	RTEfind;
	RREP(i,1<<log,1) no[i]=-(no[i<<1]+no[i<<1|1]==-2);
	RTEfind;
	int cnt = 0;
	RTEfind;
	REP(i,1,1<<log) if(no[i]!=-1) no[i]=cnt++;
	REP(i,1,1<<log) state("no[%d]=%d\n",i,no[i]);
	RTEfind;
	vector<int> X, Y; X.resize(cnt); Y.resize(cnt);
	RTEfind;
	REP(i,1,1<<log) if(no[i]!=-1) X[no[i]]=(no[i<<1]==-1?-1:-no[i<<1]-1), Y[no[i]]=(no[i<<1|1]==-1?-1:-no[i<<1|1]-1);
	RTEfind;
	int cur = -1;
	RTEfind;
	REP(i,0,N) {
	RTEfind;
		do {cur++;} while(rev(log,cur)+N<(1<<log));
		RTEfind;
		int hi = rev(log, cur) | (1<<log);
		state("cur=%d,log=%d,hi=%d\n",cur,log,hi);
		RTEfind;
		if(hi&1) Y[no[hi>>1]]=A[i];
		else X[no[hi>>1]]=A[i];
		RTEfind;
	}
	RTEfind;
	answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:18:21: warning: statement has no effect [-Wunused-value]
   18 |  #define state(...) 69
      |                     ^~
doll.cpp:22:2: note: in expansion of macro 'state'
   22 |  state("create circuit called\n");
      |  ^~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:24:2: note: in expansion of macro 'RTEfind'
   24 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:26:2: note: in expansion of macro 'RTEfind'
   26 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:28:2: note: in expansion of macro 'RTEfind'
   28 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:30:2: note: in expansion of macro 'RTEfind'
   30 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:32:2: note: in expansion of macro 'RTEfind'
   32 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:34:2: note: in expansion of macro 'RTEfind'
   34 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:36:2: note: in expansion of macro 'RTEfind'
   36 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:38:2: note: in expansion of macro 'RTEfind'
   38 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:40:2: note: in expansion of macro 'RTEfind'
   40 |  RTEfind;
      |  ^~~~~~~
doll.cpp:18:21: warning: statement has no effect [-Wunused-value]
   18 |  #define state(...) 69
      |                     ^~
doll.cpp:42:18: note: in expansion of macro 'state'
   42 |  REP(i,1,1<<log) state("no[%d]=%d\n",i,no[i]);
      |                  ^~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:43:2: note: in expansion of macro 'RTEfind'
   43 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:45:2: note: in expansion of macro 'RTEfind'
   45 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:47:2: note: in expansion of macro 'RTEfind'
   47 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:49:2: note: in expansion of macro 'RTEfind'
   49 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:51:2: note: in expansion of macro 'RTEfind'
   51 |  RTEfind;
      |  ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:53:3: note: in expansion of macro 'RTEfind'
   53 |   RTEfind;
      |   ^~~~~~~
doll.cpp:18:21: warning: statement has no effect [-Wunused-value]
   18 |  #define state(...) 69
      |                     ^~
doll.cpp:55:3: note: in expansion of macro 'state'
   55 |   state("cur=%d,log=%d,hi=%d\n",cur,log,hi);
      |   ^~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:56:3: note: in expansion of macro 'RTEfind'
   56 |   RTEfind;
      |   ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:59:3: note: in expansion of macro 'RTEfind'
   59 |   RTEfind;
      |   ^~~~~~~
doll.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 |  #define RTEfind 42
      |                  ^~
doll.cpp:61:2: note: in expansion of macro 'RTEfind'
   61 |  RTEfind;
      |  ^~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 34 ms 5084 KB Output is correct
3 Correct 31 ms 5068 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 1744 KB Output is correct
6 Correct 42 ms 7096 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 34 ms 5084 KB Output is correct
3 Correct 31 ms 5068 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 1744 KB Output is correct
6 Correct 42 ms 7096 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 66 ms 9804 KB Output is correct
9 Correct 61 ms 10076 KB Output is correct
10 Correct 82 ms 13824 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 34 ms 5084 KB Output is correct
3 Correct 31 ms 5068 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 8 ms 1744 KB Output is correct
6 Correct 42 ms 7096 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 66 ms 9804 KB Output is correct
9 Correct 61 ms 10076 KB Output is correct
10 Correct 82 ms 13824 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 75 ms 13148 KB Output is correct
15 Correct 56 ms 9192 KB Output is correct
16 Correct 77 ms 12852 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 77 ms 13256 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 52 ms 8012 KB Output is correct
3 Correct 52 ms 8068 KB Output is correct
4 Correct 70 ms 11060 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 52 ms 8012 KB Output is correct
3 Correct 52 ms 8068 KB Output is correct
4 Correct 70 ms 11060 KB Output is correct
5 Correct 75 ms 12612 KB Output is correct
6 Correct 75 ms 12328 KB Output is correct
7 Correct 79 ms 12412 KB Output is correct
8 Correct 73 ms 12052 KB Output is correct
9 Correct 52 ms 8008 KB Output is correct
10 Correct 70 ms 11824 KB Output is correct
11 Correct 70 ms 11664 KB Output is correct
12 Correct 53 ms 8776 KB Output is correct
13 Correct 55 ms 8776 KB Output is correct
14 Correct 55 ms 8780 KB Output is correct
15 Correct 57 ms 9028 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 44 ms 7276 KB Output is correct
18 Correct 56 ms 8288 KB Output is correct
19 Correct 52 ms 8268 KB Output is correct
20 Correct 71 ms 11784 KB Output is correct
21 Correct 70 ms 11564 KB Output is correct
22 Correct 70 ms 11644 KB Output is correct