oj.uz

Submission #575576

# Submission time Handle Problem Language Result Execution time Memory
575576 2022-06-11T05:33:26 Z Arvin Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 53 ms 8864 KB 
#include "Anna.h"
#include <bits/stdc++.h>
	
using namespace std;
	
#define ll long long
	
namespace {
	
int variable_example = 0;
	const int maxN = 1e5 + 5;	
}
	
void Anna(int N, std::vector<char> S) {
	// 1 as store this first X or any Z after first Xa
	// 0 otherwise
	
	vector<int> v;
	ll pos = -1;
	bool fX = false;
	for(int x=0;x<N;x++){
		if(S[x] == 'Z'){
			if(fX && (x-1 > pos) && (x+1 == N || S[x+1] != 'Z')){
				v.push_back(1);
			} else {
				v.push_back(0);
			}
			// Send(fX);
		} else if(S[x] == 'Y'){
			// Send(0);
			v.push_back(0);
		} else if(S[x] == 'X'){
			if(!fX){
				v.push_back(1);
				// Send(1);
				fX = true;
				pos = x;
			} else {
				v.push_back(0);
				// Send(0);
			}
		}
	}
	
	// guaranteed bit 1 at most N/2 + 1
	// alternating, only special case where first X and any Z are adjacent.

	// first 16 bits are location of first X
	// if not exist: ok delete all
	// else :
	// check first bit after loc
	// if 0 length is odd
	// - if one:
	// - - 
	// - else:
	
	pos++;
	for(int y=0;y<17;y++){
		if(pos&(1ll << y)){
			Send(1);
		} else {
			Send(0);
		}
	}
	
	if(pos == 0){
		return;
	}
	
	ll cnt[51];
	ll sum = 2;
    ll table[51];
    table[0] = 1; cnt[0] = 1;
    table[1] = 1; cnt[1] = 2;
    for(int x=2;x<=50;x++){
    	table[x] = 0;
		for(int y=0;y<=x-2;y++){
    		table[x] += table[y];
		}
		
		sum += table[x];
		cnt[x] = sum;
	}
	
//	cout << "... " << pos << "\n";
	while(pos < v.size()){
		ll val = 0;
		for(int x=49;x>=0;x--){
			if(pos+x < v.size() && v[pos+x] == 1){
//				cout << "+ " << x << " " << val << "+" << cnt[x] << "\n";
				val += cnt[x];
			}
		}
		
		for(int y=0;y<35;y++){
			if(val&(1ll << y)){
				Send(1);
			} else {
				Send(0);
			}
		}
		pos += 50;
	}
	// Send(v[0]);
	// bool skip = false;
	// for(int x=0;x<N;x++){
	// 	if(skip){
	// 		skip = false;
	// 		continue;
	// 	}
	
	// 	if(v[x] == 0){
	// 		if(x+1 == N || v[x+1] == 1){
	// 			Send(0);
	// 			if(x+1 < N && v[x+1] == 1) Send(1);
	// 			else Send(0);
	// 		} else {
	// 			Send(1);
	// 			if(x+2 < N && v[x+2] == 1){
	// 				Send(1);
	// 			} else {
	// 				Send(0);
	// 			}
	// 			skip = true;
	// 		}
	// 	}
	// }
}
#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

namespace {

int variable_example = 0;

int FunctionExample(int P) { return 1 - P; }

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
	ll pos = 0;
	for(int y=0;y<17;y++){
		if(A[y] == 1){
			pos += (1ll << y);
		}
	}
	
	if(pos == 0){
		for(int y=0;y<N;y++){
			Remove(y);
		}
		return;
	}
	
//	for(auto val : A){
//		cout << val << " ";
//	}cout << "\n";
	ll cnt[51];
	ll sum = 2;
    ll table[51];
    table[0] = 1; cnt[0] = 1;
    table[1] = 1; cnt[1] = 2;
    for(int x=2;x<=50;x++){
    	table[x] = 0;
		for(int y=0;y<=x-2;y++){
    		table[x] += table[y];
		}
		
		sum += table[x];
		cnt[x] = sum;
	}
	
	vector<int> v(N, 0);
	v[pos-1] = 1;
	
	ll idx = 17;
	while(idx < L){
		ll state = 0;
		for(int y=0;y<35;y++){
			if(A[idx++] == 1){
				state += (1ll << y);
			}
		}
		
//		cout << "= " << state << "\n";
		ll val = 0;
		for(int y=49;y>=0;y--){
			if(cnt[y] <= state){
//				cout << y << " " << state << "-" << cnt[y] << "\n";
				state -= cnt[y];
				val += (1ll << y);
			}	
		}
		
		for(int y=0;y<50;y++){
			if(pos+y >= N) break;
			v[pos+y] = ((val&(1ll << y)) != 0);
		}
		pos += 50;
	}
//	 for(auto val : v){
//	 	cout << val << " ";
//	 }cout << "\n";
//	 cout << v.size() << "\n";
	vector<int> ans;
	pos = -1;
	int lst = 0;
	for(int x=0;x<v.size();x++){
		if(v[x] == 1){
			if(pos == -1){
				pos = x;
				lst = x+1;
			} else {
				for(int y=x-1;y>=lst;y--){
					ans.push_back(y);
				}
				ans.push_back(x);
				lst = x+1;
			}
		}
	}
	
	for(int x=0;x<=pos;x++){
		ans.push_back(x);
	}
	for(int x=lst;x<N;x++){
		ans.push_back(x);
	}

	for(auto val : ans){
		// cout << "- " << val << "\n";
		Remove(val);
	}
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:86:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while(pos < v.size()){
      |        ~~~~^~~~~~~~~~
Anna.cpp:89:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    if(pos+x < v.size() && v[pos+x] == 1){
      |       ~~~~~~^~~~~~~~~~
Anna.cpp: At global scope:
Anna.cpp:10:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   10 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int x=0;x<v.size();x++){
      |              ~^~~~~~~~~
Bruno.cpp: At global scope:
Bruno.cpp:12:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
   12 | int FunctionExample(int P) { return 1 - P; }
      |     ^~~~~~~~~~~~~~~
Bruno.cpp:10:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   10 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 516 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 0 ms 508 KB Output is correct
5 Correct 0 ms 516 KB Output is correct
6 Correct 0 ms 520 KB Output is correct
7 Correct 0 ms 504 KB Output is correct
8 Correct 0 ms 508 KB Output is correct
9 Correct 0 ms 508 KB Output is correct
10 Correct 0 ms 508 KB Output is correct
11 Correct 0 ms 508 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 53 ms 8400 KB Partially correct
2 Partially correct 49 ms 8768 KB Partially correct
3 Incorrect 51 ms 8864 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -