oj.uz

Submission #1012494

# Submission time Handle Problem Language Result Execution time Memory
1012494 2024-07-02T08:48:01 Z Unforgettablepl Ancient Machine (JOI21_ancient_machine) C++17
99 / 100
 46 ms 9308 KB 
#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

namespace {

vector<int> fib(43);
void genFib(){
    fib[1] = 1;
    for(int i=2;i<43;i++)fib[i]=fib[i-1]+fib[i-2];
}
void blockp(vector<int> block){
    int ans = 0;
    for(int i=0;i<block.size();i++){
        if(block[i])ans+=fib[block.size()-i+1];
    }
    for(int bit=0;bit<28;bit++)Send(min(1,ans&(1<<bit)));
}
void process(vector<int> arr){
    genFib();
    for(int blocks=0;blocks<2500;blocks++){
        vector<int> curr;
        for(int i=0;i<40;i++)curr.emplace_back(arr[blocks*40+i]);
        blockp(curr);
    }
}
}

void Anna(int N, std::vector<char> S) {
    bool foundX = false;
    S.emplace_back('$');
    vector<int> bits;
    int founder = -2;
    bool edge = false;
    for(int i=0;i<N;i++){
        if(S[i]=='X'){
            if(foundX)bits.emplace_back(0);
            else {
                foundX = true;
                founder = i;
                bits.emplace_back(1);
            }
        } else if(S[i]=='Y'){
            bits.emplace_back(0);
        } else if(S[i]=='Z'){
            if(!foundX or S[i+1]=='Z' or i-1==founder){
                bits.emplace_back(0);
                if(i-1==founder and S[i+1]!='Z')edge = true;
            } else bits.emplace_back(1);
        }
    }
    while(bits.size()<100000)bits.emplace_back(0);
    process(bits);
    if(edge)Send(0);
}

#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

namespace {
vector<int> fib(43);
void genFib(){
    fib[1] = 1;
    for(int i=2;i<43;i++)fib[i]=fib[i-1]+fib[i-2];
}
vector<int> blockp(int tar){
    vector<int> ans = {0};
    for(int i=0;i<40;i++){
        if(ans.back()==0 and fib[40-i+1]<=tar){
            ans.emplace_back(1);
            tar-=fib[40-i+1];
        } else ans.emplace_back(0);
    }
    ans.erase(ans.begin());
    return ans;
}
vector<int> process(vector<int> arr){
    genFib();
    vector<int> res;
    for(int block=0;block<2500;block++){
        int curr = 0;
        for(int i=0;i<28;i++)if(arr[block*28+i])curr|=(1<<i);
        auto ans = blockp(curr);
        for(int&i:ans)res.emplace_back(i);
    }
    return res;
}
}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
    vector<int> PR;
    // Process A into PR
    PR = process(A);
    PR.erase(PR.begin()+N,PR.end());
    // Processing end
    vector<bool> vis(N);
    vector<int> po;
    for(int i=0;i<N;i++){
        if(PR[i]==1)po.emplace_back(i);
    }
    if(L==70001){
        po.insert(po.begin()+1,po[0]+1);
    }
    for(int x=1;x<po.size();x++){
        for(int i=po[x]-1;i>po[x-1];i--){
            Remove(i);
            vis[i]=true;
        }
        vis[po[x]]=true;
        Remove(po[x]);
    }
    for(int i=0;i<N;i++)if(!vis[i])Remove(i);
}

Compilation message

Anna.cpp: In function 'void {anonymous}::blockp(std::vector<int>)':
Anna.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<block.size();i++){
      |                 ~^~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int x=1;x<po.size();x++){
      |                 ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3740 KB Output is correct
2 Correct 9 ms 3992 KB Output is correct
3 Correct 9 ms 3752 KB Output is correct
4 Correct 10 ms 3756 KB Output is correct
5 Correct 9 ms 3920 KB Output is correct
6 Correct 9 ms 4004 KB Output is correct
7 Correct 9 ms 4008 KB Output is correct
8 Correct 9 ms 3996 KB Output is correct
9 Correct 9 ms 4000 KB Output is correct
10 Correct 9 ms 4020 KB Output is correct
11 Correct 9 ms 4016 KB Output is correct

Subtask #2
94.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 34 ms 9216 KB Partially correct
2 Correct 34 ms 9088 KB Output is correct
3 Partially correct 33 ms 9164 KB Partially correct
4 Correct 33 ms 9080 KB Output is correct
5 Correct 34 ms 9244 KB Output is correct
6 Correct 34 ms 9056 KB Output is correct
7 Correct 40 ms 9040 KB Output is correct
8 Partially correct 33 ms 9132 KB Partially correct
9 Correct 37 ms 9052 KB Output is correct
10 Correct 40 ms 9084 KB Output is correct
11 Partially correct 34 ms 9092 KB Partially correct
12 Partially correct 34 ms 9308 KB Partially correct
13 Correct 40 ms 9020 KB Output is correct
14 Partially correct 41 ms 9208 KB Partially correct
15 Correct 33 ms 9276 KB Output is correct
16 Partially correct 33 ms 9164 KB Partially correct
17 Correct 34 ms 8960 KB Output is correct
18 Correct 36 ms 8980 KB Output is correct
19 Correct 39 ms 9032 KB Output is correct
20 Correct 30 ms 9292 KB Output is correct
21 Correct 36 ms 9244 KB Output is correct
22 Correct 37 ms 9012 KB Output is correct
23 Partially correct 36 ms 9040 KB Partially correct
24 Partially correct 34 ms 9264 KB Partially correct
25 Correct 42 ms 9048 KB Output is correct
26 Correct 40 ms 8948 KB Output is correct
27 Correct 40 ms 8960 KB Output is correct
28 Correct 46 ms 8932 KB Output is correct
29 Correct 41 ms 9056 KB Output is correct
30 Correct 38 ms 8940 KB Output is correct
31 Correct 40 ms 9028 KB Output is correct
32 Correct 34 ms 9144 KB Output is correct
33 Partially correct 41 ms 9204 KB Partially correct