CSES - Datatähti 2017 alku - Results
Submission details
Task:Bittijono
Sender:3isagreatnumber
Submission time:2016-10-06 18:12:05 +0300
Language:C++
Status:READY
Result:29
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED19
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.10 s2details
#31.25 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:48:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < new_ks.size(); i++)
                                     ^

Code

#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#define ull unsigned long long

using namespace std;

string gen(ull);
string inv(string);

int main(void)
{
    ull n;
    cin >> n;
    vector<pair<ull, int> > new_ks;
    pair<ull, int> tmp(0,0);

    ull k;
    for (ull i = 0; i < n; i++)
    {
        cin >> k;
        ull n = ceil((log(k)/log(2)));
        ull l = pow(2, n); 

        if (k > l/2 && n%2==0)
        {
            tmp.first = l - k;
            tmp.second = 0; 
            new_ks.push_back(tmp);
        }
        else if (k > l/2 && n%2==1)
        {
            tmp.first = l - k;
            tmp.second = 1; 
            new_ks.push_back(tmp);
        }
        else
        {
            tmp.first = k;
            tmp.second = 0; 
            new_ks.push_back(tmp);
        }
        //cout << "\nfst: " << tmp.first << " snd: " << tmp.second << "\n";
    }

    ull max = 1;
    for (int i = 0; i < new_ks.size(); i++)
    {
        if (new_ks[i].first+1>max) max = new_ks[i].first;
    }

    string s = gen(max);
    //cout << "\nstring: " << s << endl;

    for (ull i = 0; i < n; i++)
    {
        if (new_ks[i].second == 0)
        {
            cout << s[new_ks[i].first] << "\n";
        }
        else
        {
            string s_tmp = "";
            s_tmp += s[new_ks[i].first];
            cout << inv(s_tmp) << "\n";
        }
    }
}

string gen(ull k_max)
{
    ull n = ceil(log(float(k_max))/log(2.0))+1;

    string s = "0";
    for (ull i = 1; i < n; i++)
    {
        s+=inv(s);
    }
    return s;
}

string inv(string s)
{
    for (ull i = 0, l = s.length(); i < l; i++)
    {
        if (s[i] == '1') s[i] = '0';
        else s[i] = '1';
    }
    return s;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
100
62
9
12
73
...

correct output
1
1
1
0
1
...

user output
1
1
1
0
1
...

Test 2

Group: 2

Verdict: ACCEPTED

input
100000
565433
141881
120108
825392
...

correct output
1
1
0
0
1
...

user output
1
1
0
0
1
...

Test 3

Group: 3

Verdict:

input
100000
374768524402011755
937067109466254318
389256426086302899
932585725667010169
...

correct output
0
1
1
1
1
...

user output
(empty)