I got AC with O(N*sqrt(N)),but my solution is very hard(274 lines and many different subtasks). Who can say simple solution(idea without code)?

После того как сайт проверил мою задачу, я решил проверить несколько частных случаев
и в одном у меня программа ломалась, но это не помешало ей пройти проверку.
Входные данные:
5 4
1 2
2 3
3 4
4 5
Ответ 2 и 23 и 45, но должно быть 2 и 12 и 45

#include <iostream>
using namespace std;

int main() {
unsigned long long n,a,b,c,s;
int i;
unsigned long long  x[100001];
memset(x,0,sizeof(x));
cin>>n;
for (i=1;i<=n+1;i++)
{
cin>>a>>b>>c;
x[a]=x[a]+c;
x[b+1]=x[b+1]-c;
};s=0;
for (i=1;i<=n;i++)
{
s=s+x[i];
if (i==n) cout<<s<<endl; else
cout<<s<<" ";
}
};

Try std::unordered_map instead of std::map. This one helped me

Where is my mistake?
I have WA on test 2!!!

#include <iostream>
using namespace std;
int main ()
{
    char c;
    int i,n,br=0,b=0,l=1;
    while (cin>>c)
    {
        if (c=='!'||c=='?'||c=='.') l=1;
        else
        {
            if (c>='a'&&c<='z')
            if (l==1) br++;
            if (c>='A'&&c<='Z')
            if (l==0) br++;
            l=0;
        }
        if (c=='!'||c=='?'||c=='.')
        {
            if (br>0) b+=1;
            br=0;
        }
    }
    cout<<b<<endl;
    return 0;
}

Spend 10 submissions to realise, that I don't return anything from function, that must return bool value

Suppose we want to calculate max({A * a[i] + B * a[i + 1], A * a[i + 1] + B * a[i]}) for i = 0..n-1 (in this problem A = 0, B = 1). Then answer(A, B, n) = max(answer(max(A, B), A + B, n/2), A * a[n - 1] + B * a[n], B * a[n - 1] + A * a[n]), so it can be solved recursively.

Sort elements by count and use some combinatorics

What happens when the order is greater than 1e9? Wouldn't a permutation with cycle lengths equal to first N primes easily exceed order 1e9? For example lcm ( 3, 5, 7.. 29 )

Got this by first try, I didn't opened IDE, didnt'y opened even notepad. I wrote it right in the input box. Too easy.

Always got TLE 43. I've tried different optimization on python, but nothing work. C++ with same code and std::getline optimization got AC with almost TLE 300-350msec. And as I see no one has AC with Python =\

5
2 0
1 3 0
2 0
5 0
4 0

I tried to solve this task by dp and bfs, but always have a TL on test 3.

what the data test 9

Even after reading all the posts here. Please help.
1. assert program is shorter than input
2. assert no long lines in source code
3. split string literal into vectors
4. assert no '\r' but '\n' after reading input
5. output with std::cout and '\n'
6. many tests and asserts

===this is an example of archive===
might be overkill to use Huffman and base64
shorten variable names in actual archive
===================================
//CPP
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int length = 37;
std::vector<std::string> encoded{
"7VKh",
"7lg="
};
std::unordered_map<std::string, char> table{
{"00", 'o'},
{"01", 'l'},
{"100", 'w'},
{"1010", ' '},
{"1011", '!'},
{"1100", 'd'},
{"1101", 'e'},
{"1110", 'h'},
{"1111", 'r'}
};

struct HuffmanTree {
    char ch;
    struct HuffmanTree* left;
    struct HuffmanTree* right;
    ~HuffmanTree() {
        delete left;
        delete right;
    }
};

void build_tree(HuffmanTree* root, std::string code, char ch)
{
    auto node{root};
    for (auto x : code)
        if (x == '1') {
            if (node->right == nullptr)
                node->right = new HuffmanTree();
            node = node->right;
        } else {
            if (node->left == nullptr)
                node->left = new HuffmanTree();
            node = node->left;
        }
    node->ch = ch;
}

char lookup(std::vector<bool>::iterator& it, const HuffmanTree* tree)
{
    auto node{tree};
    while (true) {
        if (node->left == nullptr)
            break;
        if (*it)
            node = node->right;
        else
            node = node->left;
        it++;
    }
    return node->ch;
}

void huffman_decode(std::vector<bool> bits, const HuffmanTree* tree)
{
    auto it{bits.begin()};
    while (it != bits.end())
        std::cout << lookup(it, tree);
}

int six(char c)
{
    if (c >= 'A' and c <= 'Z')
        return c-'A';
    if (c >= 'a' and c <= 'z')
        return c-'a' + 26;
    if (c >= '0' and c <= '9')
        return c-'0' + 52;
    if (c == '+')
        return 62;
    if (c == '/')
        return 63;
    return 0;
}

std::vector<std::string> base64_decode(std::vector<std::string> encoded)
{
    std::vector<std::string> decoded;
    for (auto s : encoded) {
        std::string t;
        auto i{0u};
        while (i < s.size()) {
            auto p0{six(s[i])};
            auto p1{six(s[i+1])};
            auto p2{six(s[i+2])};
            auto p3{six(s[i+3])};
            t.push_back((p0<<2) + ((p1&0x30)>>4));
            if (s[i+2] != '=')
                t.push_back(((p1&0x0f)<<4) + ((p2&0x3c)>>2));
            if (s[i+3] != '=')
                t.push_back(((p2&0x03)<<6) + p3);
            i += 4;
        }
        decoded.push_back(t);
    }
    return decoded;
}

std::vector<bool> string_to_bits(int n, std::vector<std::string> v)
{
    std::vector<bool> bits;
    for (auto s : v)
        for (auto byte : s)
            for (auto i{7}; i >= 0; i--)
                bits.push_back((byte >> i) & 1);
    while (int(bits.size()) > n)
        bits.pop_back();
    return bits;
}

int main()
{
    auto decoded{base64_decode(encoded)};
    auto bits{string_to_bits(length, decoded)};
    auto root{new HuffmanTree()};
    for (auto [code, ch] : table)
        build_tree(root, code, ch);
    huffman_decode(bits, root);
}

Is there any way I can see the output of my program? The message "Runtime error" is very uninformative, besides, on my computer, my program performs a variety of tests without any errors.

Can you give me some tests,please?
I can't find any solutions on the internet.




Edited by author 03.05.2021 09:14

Tests?

Edited by author 03.11.2019 21:42

Edited by author 03.11.2019 21:42