oj.uz

Submission #677097

# Submission time Handle Problem Language Result Execution time Memory
677097 2023-01-02T09:10:51 Z alvingogo Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 55 ms 8668 KB 
#include <bits/stdc++.h>
#include "Anna.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<long long> v;
const int A=51,B=73;
void init(){
	v.clear();
	v.push_back(1);
	v.push_back(1);
	for(int i=0;i<74;i++){
		long long u=v[i]+v[i+1];
		if(u>1e18){
			break;
		}
		v.push_back(u);
	}
}
void sei(long long a){
	for(int i=A-1;i>=0;i--){
		if(a>=(1ll<<i)){
			a-=(1ll<<i);
			Send(1);
		}
		else{
			Send(0);
		}
	}
}
void Anna(int n,vector<char> s){
	init();
	string a;
	int flag=0;
	for(int i=0;i<n;i++){
		if(s[i]=='X'){
			if(flag==0){
				flag=1;
				a+='1';
				a+='0';
			}
			else{
				a+='0';
			}
		}
		else if(s[i]=='Y'){
			a+='0';
		}
		else{
			if(i+1<n && s[i]==s[i+1]){
				a+='0';
				continue;
			}
			if(flag){
				a+='1';
			}
			else{
				a+='0';
			}
		}
	}
	int g=a.size();
	while(g%B!=0){
		g++;
		a+='0';
	}
	for(int i=0;i<g/B;i++){
		long long x=0;
		for(int j=0;j<B;j++){
			if(a[i*B+j]=='1'){
				x+=v[B-j];
			}
		}
		assert(x<=(1ll<<A));
		//cout << x << "\n";
		sei(x);
	}
}
#include <bits/stdc++.h>
#include "Bruno.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<long long> v2;
const int A=51,B=73;
void init2(){
	v2.clear();
	v2.push_back(1);
	v2.push_back(1);
	for(int i=0;i<74;i++){
		long long u=v2[i]+v2[i+1];
		if(u>1e18){
			break;
		}
		v2.push_back(u);
	}
}

void Bruno(int n,int l,vector<int> a){
    init2();
    string s;
    for(int i=0;i<l/A;i++){
        long long zz=1ll<<(A-1);
        long long x=0;
        for(int j=0;j<A;j++){
            if(a[i*A+j]==1){
                x+=zz;
            }
            zz>>=1;
        }
        //cout << x << "\n";
        for(int j=B;j>=1;j--){
            if(x>=v2[j]){
                x-=v2[j];
                s+='1';
            }
            else{
                s+='0';
            }
        }
    }
    int m=0;
    int flag=0;
    vector<int> gg(n);
    for(int i=0;i<n;i++){
        if(s[i+m]=='1'){
            gg[i]=1;
            flag=1;
            m=1;
        }
        else{
            gg[i]=0;
        }
    }
    vector<int> vis(n);
    flag=0;
    int lf=0;
    for(int i=0;i<n;i++){
        if(gg[i]==1){
            if(flag){
                for(int j=i-1;j>lf;j--){
                    Remove(j);
                    vis[j]=1;
                }
                Remove(i);
                vis[i]=1;
            }
            flag=1;
            lf=i;
        }
    }
    for(int i=0;i<n;i++){
        if(!vis[i]){
            Remove(i);
        }
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8192 KB Output is correct
2 Correct 52 ms 8564 KB Output is correct
3 Correct 49 ms 8548 KB Output is correct
4 Correct 49 ms 8632 KB Output is correct
5 Correct 48 ms 8616 KB Output is correct
6 Correct 49 ms 8568 KB Output is correct
7 Correct 47 ms 8604 KB Output is correct
8 Correct 49 ms 8660 KB Output is correct
9 Correct 49 ms 8580 KB Output is correct
10 Correct 48 ms 8668 KB Output is correct
11 Correct 48 ms 8564 KB Output is correct
12 Correct 49 ms 8556 KB Output is correct
13 Correct 54 ms 8568 KB Output is correct
14 Correct 55 ms 8608 KB Output is correct
15 Correct 49 ms 8608 KB Output is correct
16 Correct 51 ms 8564 KB Output is correct
17 Correct 54 ms 8556 KB Output is correct
18 Correct 54 ms 8628 KB Output is correct
19 Correct 53 ms 8560 KB Output is correct
20 Correct 47 ms 8568 KB Output is correct
21 Correct 48 ms 8628 KB Output is correct
22 Correct 55 ms 8564 KB Output is correct
23 Correct 48 ms 8656 KB Output is correct
24 Correct 47 ms 8652 KB Output is correct
25 Correct 53 ms 8448 KB Output is correct
26 Correct 55 ms 8608 KB Output is correct
27 Correct 54 ms 8560 KB Output is correct
28 Correct 54 ms 8636 KB Output is correct
29 Correct 54 ms 8588 KB Output is correct
30 Correct 54 ms 8584 KB Output is correct
31 Correct 54 ms 8560 KB Output is correct
32 Correct 47 ms 8592 KB Output is correct
33 Correct 48 ms 8544 KB Output is correct