oj.uz

Submission #762223

# Submission time Handle Problem Language Result Execution time Memory
762223 2023-06-21T05:39:56 Z minhcool Mechanical Doll (IOI18_doll) C++17
75.5458 / 100
 116 ms 27128 KB 
//#define local
#ifndef local
#include "doll.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 5e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int cnt = 0;

int c[N], x[N], y[N];

vector<int> nxts[N];

int rt;

void create(int where, vector<int> v){
//	cout << "OKOKOK " << where << " " << v.size() << "\n";
	if(v.size() == 2){
	//	cout << v[0] << " " << v[1] << "\n";
		x[where] = v[0], y[where] = v[1];
		return;
	}
	vector<int> v1, v2;
	//cnt++;
	//x[where] = -cnt;
	for(int i = 0; i < v.size(); i += 2) v1.pb(v[i]);
	bool ck = 0;
	for(auto it : v1) ck |= (it >= 0);
	if(ck){	
		cnt++;
		x[where] = -cnt;
		create(cnt, v1);
	}
	else x[where] = rt;
	for(int i = 1; i < v.size(); i += 2) v2.pb(v[i]);
	ck = 0;
	for(auto it : v2) ck |= (it >= 0);
	if(ck){	
		cnt++;
		y[where] = -cnt;
		create(cnt, v2);
	}
	else y[where] = rt;
}

void create_circuit(int M, vector<int> A){
 	A.pb(0);
  	for(int i = 0; (i + 1) < A.size(); i++) nxts[A[i]].pb(A[i + 1]);
  	c[0] = A[0];
  	int cntt = 0;
  	for(int i = 1; i <= M; i++){
  		if(nxts[i].size() == 0) nxts[i].pb(1);
  		if(nxts[i].size() <= 1){
  			c[i] = nxts[i][0];
  			continue;
		}
		int pw = 1;
		while(pw < nxts[i].size()) pw *= 2;
		cntt += (pw - 1);
		//cnt++;
		//c[i] = -cnt;
		//create(cnt, nxts[i]);
	}
//	cout << "HEHE " << cntt << "\n";
//	cout << cntt << "\n";
	int temp = cntt;
	for(int i = 1; i <= M; i++){
		if(nxts[i].size() <= 1) continue;
		int pw = 1;
		while(pw < nxts[i].size()) pw *= 2;
		cnt++;
		c[i] = -cnt;
		rt = -cnt;
		if(pw > nxts[i].size()){
		vector<int> nw;
		reverse(nxts[i].begin(), nxts[i].end());
		int cnt = pw - nxts[i].size();
		for(int j = 0; j < pw; j++){
			if(!(j & 1)){
				if(cnt){
					nw.pb(rt);
					cnt--;
				}
				else{
				//	assert(nxts[i].size());
					nw.pb(nxts[i].back());
					nxts[i].pop_back();
				}
			}
			else{
			//	assert(nxts[i].size());
				nw.pb(nxts[i].back());
				nxts[i].pop_back();
			}
		}
		nxts[i] = nw;
		//reverse(nxts[i].begin(), nxts[i].end());
		//cntt++;
		//reverse(nxts[i].begin(), nxts[i].end());
	}
		//cnt++;
		create(cnt, nxts[i]);
	}
	/*
	for(int i = 1; i <= cnt; i++){
		if(x[i] < -cnt) x[i] = (-(cnt + (-x[i]) - temp)); 
		if(y[i] < -cnt) x[i] = (-(cnt + (-x[i]) - temp)); 
	}
	for(int i = temp + 1; i <= cntt; i++){
		x[i - (temp - cnt)] = x[i];
		y[i - (temp - cnt)] = y[i];
	}*/
//	cout << cnt << "\n";
	vector<int> C(M + 1), X(cnt), Y(cnt);
	for(int i = 0; i <= M; i++) C[i] = c[i];
	for(int i = 1; i <= cnt; i++){
		X[i - 1] = x[i], Y[i - 1] = y[i];
	}
	answer(C, X, Y);
}

#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
#endif

Compilation message

doll.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
doll.cpp: In function 'void create(int, std::vector<int>)':
doll.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0; i < v.size(); i += 2) v1.pb(v[i]);
      |                 ~~^~~~~~~~~~
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 1; i < v.size(); i += 2) v2.pb(v[i]);
      |                 ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int i = 0; (i + 1) < A.size(); i++) nxts[A[i]].pb(A[i + 1]);
      |                   ~~~~~~~~^~~~~~~~~~
doll.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while(pw < nxts[i].size()) pw *= 2;
      |         ~~~^~~~~~~~~~~~~~~~
doll.cpp:93:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   while(pw < nxts[i].size()) pw *= 2;
      |         ~~~^~~~~~~~~~~~~~~~
doll.cpp:97:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   if(pw > nxts[i].size()){
      |      ~~~^~~~~~~~~~~~~~~~
doll.cpp:89:6: warning: unused variable 'temp' [-Wunused-variable]
   89 |  int temp = cntt;
      |      ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 34 ms 17680 KB Output is correct
3 Correct 26 ms 16196 KB Output is correct
4 Correct 6 ms 12044 KB Output is correct
5 Correct 17 ms 16704 KB Output is correct
6 Correct 29 ms 18324 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 34 ms 17680 KB Output is correct
3 Correct 26 ms 16196 KB Output is correct
4 Correct 6 ms 12044 KB Output is correct
5 Correct 17 ms 16704 KB Output is correct
6 Correct 29 ms 18324 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 39 ms 19780 KB Output is correct
9 Correct 43 ms 20588 KB Output is correct
10 Correct 57 ms 23924 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 12020 KB Output is correct
13 Correct 5 ms 12004 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 34 ms 17680 KB Output is correct
3 Correct 26 ms 16196 KB Output is correct
4 Correct 6 ms 12044 KB Output is correct
5 Correct 17 ms 16704 KB Output is correct
6 Correct 29 ms 18324 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 39 ms 19780 KB Output is correct
9 Correct 43 ms 20588 KB Output is correct
10 Correct 57 ms 23924 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 6 ms 12020 KB Output is correct
13 Correct 5 ms 12004 KB Output is correct
14 Correct 82 ms 26836 KB Output is correct
15 Correct 45 ms 19528 KB Output is correct
16 Correct 68 ms 23724 KB Output is correct
17 Correct 6 ms 11988 KB Output is correct
18 Correct 7 ms 12056 KB Output is correct
19 Correct 6 ms 12056 KB Output is correct
20 Correct 71 ms 25204 KB Output is correct
21 Correct 6 ms 11988 KB Output is correct
22 Correct 5 ms 11988 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
12.4214219136 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 51 ms 20232 KB Output is correct
3 Correct 52 ms 20880 KB Output is correct
4 Partially correct 89 ms 27128 KB Output is partially correct

Subtask #6
37.1243889072 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 51 ms 20232 KB Output is correct
3 Correct 52 ms 20880 KB Output is correct
4 Partially correct 89 ms 27128 KB Output is partially correct
5 Partially correct 116 ms 25360 KB Output is partially correct
6 Partially correct 92 ms 25024 KB Output is partially correct
7 Partially correct 91 ms 25152 KB Output is partially correct
8 Partially correct 88 ms 24508 KB Output is partially correct
9 Partially correct 52 ms 20060 KB Output is partially correct
10 Partially correct 81 ms 24268 KB Output is partially correct
11 Partially correct 75 ms 23304 KB Output is partially correct
12 Partially correct 50 ms 19432 KB Output is partially correct
13 Partially correct 60 ms 20616 KB Output is partially correct
14 Partially correct 62 ms 20680 KB Output is partially correct
15 Partially correct 68 ms 20812 KB Output is partially correct
16 Partially correct 8 ms 12332 KB Output is partially correct
17 Partially correct 57 ms 19680 KB Output is partially correct
18 Partially correct 59 ms 19432 KB Output is partially correct
19 Partially correct 63 ms 20520 KB Output is partially correct
20 Partially correct 90 ms 23688 KB Output is partially correct
21 Partially correct 91 ms 25020 KB Output is partially correct
22 Partially correct 83 ms 24124 KB Output is partially correct