oj.uz

Submission #101740

# Submission time Handle Problem Language Result Execution time Memory
101740 2019-03-19T17:30:38 Z baluteshih Mechanical Doll (IOI18_doll) C++14
100 / 100
 173 ms 10892 KB 
#include "doll.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> C,X,Y,pl[100005];
bool state[400005];
const int INF=1e9;

int newnode()
{
	X.pb(INF),Y.pb(INF);
	return -(int)(X.size());
}
 
int node(int x)
{
	if(x==2) return newnode();
	int tmp=newnode();
	int a=node(x/2),b=node(x/2);
	X[-tmp-1]=a,Y[-tmp-1]=b;
	return tmp;
}
 
void walk(vector<int> &v,int st)
{
	int k=0;
	int pos=st;
	while(k<v.size())
	{
	    state[-pos] = !state[-pos];
	    if(state[-pos])
	    	if(X[-(1+pos)]!=INF) pos=X[-(1+pos)];
	    	else X[-(1+pos)]=v[k++],pos=st;
	   	else
	    	if(Y[-(1+pos)]!=INF) pos=Y[-(1+pos)];
	    	else Y[-(1+pos)]=v[k++],pos=st;
	}
}

int r_node(vector<int> &v)
{
	int tmp,sz=v.size();
	if(!(sz&(sz-1))) tmp=node(sz);
	else
	{
		int nw=tmp=newnode(),lb=sz&-sz,a;
		for(int i=1<<__lg(sz);i>lb;i>>=1)
		{
			if(v.size()&i)
				a=node(i),X[-nw-1]=a;
			else
				X[-nw-1]=tmp;
			a=newnode(),Y[-nw-1]=a,nw=Y[-nw-1];
		}
		X[-nw-1]=tmp;
		if(lb>1) a=node(lb),Y[-nw-1]=a;
	}
	walk(v,tmp);
	return tmp;
}

void create_circuit(int M, std::vector<int> A) {
	C.resize(M+1);
	C[0]=A[0];
	if(A.size()==1)
		C[1]=0;
	else
	{
		for(int i=0;i+1<A.size();++i)
			A[i]=A[i+1];
		A.back()=0;
		int tmp=r_node(A);
		for(int i=1;i<=M;++i)
			C[i]=tmp;
	}
	answer(C,X,Y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 48 ms 6080 KB Output is correct
3 Correct 47 ms 6308 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 21 ms 3788 KB Output is correct
6 Correct 73 ms 7232 KB Output is correct
7 Correct 4 ms 2592 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 48 ms 6080 KB Output is correct
3 Correct 47 ms 6308 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 21 ms 3788 KB Output is correct
6 Correct 73 ms 7232 KB Output is correct
7 Correct 4 ms 2592 KB Output is correct
8 Correct 84 ms 7984 KB Output is correct
9 Correct 110 ms 9540 KB Output is correct
10 Correct 142 ms 10892 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 48 ms 6080 KB Output is correct
3 Correct 47 ms 6308 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 21 ms 3788 KB Output is correct
6 Correct 73 ms 7232 KB Output is correct
7 Correct 4 ms 2592 KB Output is correct
8 Correct 84 ms 7984 KB Output is correct
9 Correct 110 ms 9540 KB Output is correct
10 Correct 142 ms 10892 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 129 ms 10372 KB Output is correct
15 Correct 96 ms 8492 KB Output is correct
16 Correct 133 ms 10056 KB Output is correct
17 Correct 3 ms 2636 KB Output is correct
18 Correct 3 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 173 ms 10536 KB Output is correct
21 Correct 4 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 76 ms 7096 KB Output is correct
3 Correct 83 ms 7496 KB Output is correct
4 Correct 128 ms 9264 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 76 ms 7096 KB Output is correct
3 Correct 83 ms 7496 KB Output is correct
4 Correct 128 ms 9264 KB Output is correct
5 Correct 148 ms 9956 KB Output is correct
6 Correct 140 ms 9712 KB Output is correct
7 Correct 138 ms 9740 KB Output is correct
8 Correct 155 ms 9472 KB Output is correct
9 Correct 92 ms 7480 KB Output is correct
10 Correct 137 ms 9332 KB Output is correct
11 Correct 128 ms 9180 KB Output is correct
12 Correct 96 ms 7792 KB Output is correct
13 Correct 80 ms 7196 KB Output is correct
14 Correct 84 ms 8204 KB Output is correct
15 Correct 88 ms 8364 KB Output is correct
16 Correct 5 ms 2764 KB Output is correct
17 Correct 88 ms 7016 KB Output is correct
18 Correct 79 ms 7000 KB Output is correct
19 Correct 85 ms 7788 KB Output is correct
20 Correct 125 ms 9276 KB Output is correct
21 Correct 119 ms 9264 KB Output is correct
22 Correct 123 ms 9208 KB Output is correct