oj.uz

Submission #334048

# Submission time Handle Problem Language Result Execution time Memory
334048 2020-12-08T07:43:30 Z nicholask Mechanical Doll (IOI18_doll) C++14
53 / 100
 114 ms 12292 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
/*
void answer(vector <int> c,vector <int> x,vector <int> y){
	cout<<"C: ";
	for (auto&i:c) cout<<i<<' ';
	cout<<endl;
	cout<<"X: ";
	for (auto&i:x) cout<<i<<' ';
	cout<<endl;
	cout<<"Y: ";
	for (auto&i:y) cout<<i<<' ';
	cout<<endl;
	return;
}
*/
void create_circuit(int m,vector <int> a){
	int n=a.size();
	int cnt[m+1]={};
	for (auto&i:a) cnt[i]++;
	bool can=1;
	for (int i=1; i<=m; i++){
		if (cnt[i]>4){
			can=0;
			break;
		}
	}
	if (can){
		vector <int> c(m+1,0),x,y;
		c[0]=a[0];
		a.push_back(0);
		vector <int> nxt[m+1];
		for (int i=0; i<n; i++) nxt[a[i]].push_back(a[i+1]);
		int cur=0;
		for (int i=1; i<=m; i++){
			if (nxt[i].size()==1){
				c[i]=nxt[i][0];
			} else if (nxt[i].size()==2){
				cur--;
				c[i]=cur;
				x.push_back(nxt[i][0]);
				y.push_back(nxt[i][1]);
			} else if (nxt[i].size()==3){
				cur--;
				c[i]=cur;
				cur--;
				x.push_back(cur);
				cur--;
				y.push_back(cur);
				x.push_back(c[i]);
				y.push_back(nxt[i][1]);
				x.push_back(nxt[i][0]);
				y.push_back(nxt[i][2]);
			} else if (nxt[i].size()==4){
				cur--;
				c[i]=cur;
				cur--;
				x.push_back(cur);
				cur--;
				y.push_back(cur);
				x.push_back(nxt[i][0]);
				y.push_back(nxt[i][2]);
				x.push_back(nxt[i][1]);
				y.push_back(nxt[i][3]);
			}
		}
		answer(c,x,y);
		return;	
	} else {
		vector <int> c(m+1,-1);
		int ts=1;
		while (ts<=n) ts<<=1;
		ts>>=1;
		vector <int> x(ts+ts,-1),y(ts+ts,-1);
		for (int i=1; i<ts; i++){
			x[i]=-1*(2*i);
			y[i]=-1*(2*i+1);
		}
		for (int i=0; i<n; i++){
			int i1=i,cur=1;
			while (cur<ts){
				cur<<=1;
				if (i1&1) cur++;
				i1>>=1;
			}
			if (i1&1) y[cur]=a[i];
			else x[cur]=a[i];
		}
		int cur=1;
		while (cur<ts){
			cur<<=1;
			cur++;
		}
		y[cur]=0;
		x.erase(x.begin());
		y.erase(y.begin());
		answer(c,x,y);
		return;
	}
}
/*
int main(){
	int n,m;
	cin>>m>>n;
	vector <int> a;
	for (int i=0; i<n; i++){
		int t;
		cin>>t;
		a.push_back(t);
	}
	create_circuit(m,a);
}
*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 47 ms 6732 KB Output is correct
3 Correct 27 ms 5420 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 42 ms 8020 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 47 ms 6732 KB Output is correct
3 Correct 27 ms 5420 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 42 ms 8020 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 55 ms 7992 KB Output is correct
9 Correct 65 ms 9128 KB Output is correct
10 Correct 93 ms 12292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 47 ms 6732 KB Output is correct
3 Correct 27 ms 5420 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 4172 KB Output is correct
6 Correct 42 ms 8020 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 55 ms 7992 KB Output is correct
9 Correct 65 ms 9128 KB Output is correct
10 Correct 93 ms 12292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 100 ms 11696 KB Output is correct
15 Correct 67 ms 6864 KB Output is correct
16 Correct 90 ms 8996 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 102 ms 11184 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 204 KB Output is partially correct
2 Partially correct 72 ms 7500 KB Output is partially correct
3 Partially correct 71 ms 7464 KB Output is partially correct
4 Partially correct 95 ms 8004 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 204 KB Output is partially correct
2 Partially correct 72 ms 7500 KB Output is partially correct
3 Partially correct 71 ms 7464 KB Output is partially correct
4 Partially correct 95 ms 8004 KB Output is partially correct
5 Partially correct 90 ms 8620 KB Output is partially correct
6 Partially correct 91 ms 8372 KB Output is partially correct
7 Partially correct 112 ms 8372 KB Output is partially correct
8 Partially correct 105 ms 8088 KB Output is partially correct
9 Partially correct 72 ms 7364 KB Output is partially correct
10 Partially correct 96 ms 8028 KB Output is partially correct
11 Partially correct 96 ms 7988 KB Output is partially correct
12 Partially correct 85 ms 7452 KB Output is partially correct
13 Partially correct 81 ms 7592 KB Output is partially correct
14 Partially correct 77 ms 7720 KB Output is partially correct
15 Partially correct 79 ms 7860 KB Output is partially correct
16 Partially correct 3 ms 460 KB Output is partially correct
17 Correct 47 ms 4420 KB Output is correct
18 Partially correct 79 ms 7468 KB Output is partially correct
19 Partially correct 101 ms 7472 KB Output is partially correct
20 Partially correct 114 ms 7984 KB Output is partially correct
21 Partially correct 90 ms 7984 KB Output is partially correct
22 Partially correct 86 ms 7996 KB Output is partially correct