oj.uz

답안 #415491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415491 2021-06-01T07:20:11 Z baluteshih 자동 인형 (IOI18_doll) C++14
100 / 100
 140 ms 10880 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:13: 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:22: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 46 ms 6168 KB Output is correct
3 Correct 46 ms 6272 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 89 ms 7256 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 46 ms 6168 KB Output is correct
3 Correct 46 ms 6272 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 89 ms 7256 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 95 ms 7988 KB Output is correct
9 Correct 92 ms 9516 KB Output is correct
10 Correct 129 ms 10880 KB Output is correct
11 Correct 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 46 ms 6168 KB Output is correct
3 Correct 46 ms 6272 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 89 ms 7256 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 95 ms 7988 KB Output is correct
9 Correct 92 ms 9516 KB Output is correct
10 Correct 129 ms 10880 KB Output is correct
11 Correct 3 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 132 ms 10332 KB Output is correct
15 Correct 103 ms 8508 KB Output is correct
16 Correct 128 ms 10052 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 129 ms 10564 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 3 ms 2636 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 4 ms 2636 KB Output is correct
6 Correct 3 ms 2636 KB Output is correct
7 Correct 2 ms 2596 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 82 ms 6996 KB Output is correct
3 Correct 77 ms 7456 KB Output is correct
4 Correct 124 ms 9300 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2636 KB Output is correct
2 Correct 82 ms 6996 KB Output is correct
3 Correct 77 ms 7456 KB Output is correct
4 Correct 124 ms 9300 KB Output is correct
5 Correct 137 ms 9892 KB Output is correct
6 Correct 135 ms 9720 KB Output is correct
7 Correct 128 ms 9856 KB Output is correct
8 Correct 123 ms 9472 KB Output is correct
9 Correct 78 ms 7488 KB Output is correct
10 Correct 131 ms 9392 KB Output is correct
11 Correct 126 ms 9264 KB Output is correct
12 Correct 91 ms 7784 KB Output is correct
13 Correct 80 ms 7240 KB Output is correct
14 Correct 88 ms 8292 KB Output is correct
15 Correct 87 ms 8360 KB Output is correct
16 Correct 4 ms 2764 KB Output is correct
17 Correct 80 ms 6908 KB Output is correct
18 Correct 81 ms 7092 KB Output is correct
19 Correct 82 ms 7740 KB Output is correct
20 Correct 140 ms 9332 KB Output is correct
21 Correct 124 ms 9296 KB Output is correct
22 Correct 125 ms 9216 KB Output is correct