Code Submission Evaluation System Login

Datatähti 2018 alku

Start:2017-10-02 00:00:00
End:2017-10-16 00:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2018 alku - Results
History
2017-10-15 23:48:4849
2017-10-15 23:37:5949
2017-10-15 23:31:3449
2017-10-15 23:26:3549
2017-10-15 23:22:3842
2017-10-15 23:15:4242
2017-10-15 23:08:3249
2017-10-15 23:04:1449
2017-10-15 22:56:3049
2017-10-14 22:49:0249
2017-10-14 22:35:1249
2017-10-14 22:33:1549
2017-10-14 22:21:3549
2017-10-14 22:19:5849
2017-10-14 22:13:0822
2017-10-14 22:12:5049
2017-10-14 22:10:0949
2017-10-14 22:07:5649
2017-10-14 21:59:5949
2017-10-14 21:59:090
2017-10-14 00:15:3049
2017-10-14 00:11:1949
2017-10-13 23:57:4949
2017-10-13 18:04:3349
2017-10-11 21:42:5949
2017-10-11 19:44:2449
2017-10-11 19:39:3949
2017-10-11 19:27:230
2017-10-11 19:26:460
2017-10-11 19:25:29
2017-10-11 19:15:0449
2017-10-11 19:01:200
2017-10-11 13:45:4949
2017-10-11 13:43:1449
2017-10-11 13:42:0949
2017-10-11 13:41:31
2017-10-11 13:34:5549
2017-10-11 13:34:4449
2017-10-11 13:34:2749
2017-10-11 13:32:53
2017-10-11 13:32:44
2017-10-11 13:32:35
2017-10-11 13:32:2622
2017-10-11 13:30:58
2017-10-11 13:30:3749
2017-10-11 13:30:2749
2017-10-11 13:27:1422
2017-10-11 13:25:3522
2017-10-11 13:21:070
2017-10-11 13:17:4849
2017-10-11 13:17:410
2017-10-11 13:16:1222
2017-10-11 13:15:5449
2017-10-11 13:15:4649
2017-10-11 13:08:1449
2017-10-11 12:42:3649
2017-10-11 12:38:5149
2017-10-11 12:36:3149
2017-10-11 12:32:130
2017-10-11 12:24:1949
2017-10-11 10:33:1449
2017-10-11 10:30:1749
2017-10-10 22:43:2449
2017-10-10 22:43:0349
2017-10-10 22:35:5949
2017-10-10 22:16:307
2017-10-10 20:28:0849
2017-10-10 18:39:3149
2017-10-10 18:39:07
2017-10-10 18:36:1049
2017-10-10 18:34:57
2017-10-10 18:34:36
2017-10-10 17:18:2149
2017-10-10 17:17:1549
2017-10-10 17:12:59
2017-10-10 16:52:3349
2017-10-10 16:32:1249
2017-10-10 10:58:4249
2017-10-10 10:55:2142
2017-10-10 10:34:3949
2017-10-10 10:27:3949
2017-10-10 10:15:3049
2017-10-10 09:52:3849
2017-10-10 09:51:350
2017-10-10 09:49:060
2017-10-10 09:39:5949
2017-10-09 21:34:2949
2017-10-09 21:27:5149
2017-10-09 14:25:4449
2017-10-09 14:20:0349
2017-10-09 14:17:5749
2017-10-09 14:13:5549
2017-10-09 13:52:5822
2017-10-09 13:27:3722
2017-10-09 13:26:1022
2017-10-09 13:23:2322
2017-10-09 13:20:3022
2017-10-09 13:11:2722
2017-10-09 12:57:0122
2017-10-09 11:58:2722
2017-10-09 11:56:5322
2017-10-08 23:28:5622
2017-10-08 23:26:4222
2017-10-08 22:57:3122
2017-10-08 22:53:580
2017-10-08 22:42:5522
2017-10-08 20:07:3722
2017-10-08 20:05:5022
2017-10-08 20:02:4122
2017-10-08 19:35:3922
2017-10-08 19:14:3822
2017-10-08 18:37:2822
2017-10-08 18:32:1822
2017-10-08 18:26:3215
2017-10-08 15:53:4322
2017-10-07 23:25:5722
2017-10-07 23:24:380
2017-10-07 23:20:320
2017-10-07 18:20:3922
2017-10-07 18:18:350
2017-10-07 12:27:010
2017-10-07 12:25:170
2017-10-07 12:10:1522
2017-10-04 18:56:1222
Task:Bittijono
Sender:inkeri
Submission time:2017-10-15 23:48:48
Language:C++
Status:READY
Score:49

Feedback

groupverdictscore
#1ACCEPTED7
#2ACCEPTED15
#3ACCEPTED27
#4TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.06 / 1.001details
#2ACCEPTED0.05 / 1.001details
#3ACCEPTED0.05 / 1.001details
#4ACCEPTED0.06 / 1.001details
#5ACCEPTED0.06 / 1.001details
#6ACCEPTED0.04 / 1.001details
#7ACCEPTED0.05 / 1.001details
#8ACCEPTED0.05 / 1.001details
#9ACCEPTED0.06 / 1.001details
#10ACCEPTED0.04 / 1.001details
#11ACCEPTED0.06 / 1.002details
#12ACCEPTED0.05 / 1.002details
#13ACCEPTED0.05 / 1.002details
#14ACCEPTED0.05 / 1.002details
#15ACCEPTED0.06 / 1.002details
#16ACCEPTED0.04 / 1.002details
#17ACCEPTED0.06 / 1.002details
#18ACCEPTED0.06 / 1.002details
#19ACCEPTED0.05 / 1.002details
#20ACCEPTED0.06 / 1.002details
#21ACCEPTED0.06 / 1.003details
#22ACCEPTED0.07 / 1.003details
#23ACCEPTED0.08 / 1.003details
#24ACCEPTED0.06 / 1.003details
#25ACCEPTED0.05 / 1.003details
#26ACCEPTED0.09 / 1.003details
#27ACCEPTED0.06 / 1.003details
#28ACCEPTED0.09 / 1.003details
#29ACCEPTED0.07 / 1.003details
#30ACCEPTED0.05 / 1.003details
#31TIME LIMIT EXCEEDED-- / 1.004details
#32TIME LIMIT EXCEEDED-- / 1.004details
#33TIME LIMIT EXCEEDED-- / 1.004details
#34TIME LIMIT EXCEEDED-- / 1.004details
#35TIME LIMIT EXCEEDED-- / 1.004details
#36TIME LIMIT EXCEEDED-- / 1.004details
#37TIME LIMIT EXCEEDED-- / 1.004details
#38TIME LIMIT EXCEEDED-- / 1.004details
#39TIME LIMIT EXCEEDED-- / 1.004details
#40TIME LIMIT EXCEEDED-- / 1.004details

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll alijonot(string bj, ll tavoite) {
    ll maara = 0;
    ll uusia0 = 1;
    ll uusia1 = 1;
    for (unsigned long long i = 0; i < bj.length(); i++) {
        char c = bj[i];
        if (c == '1') {
            maara += uusia1;
            uusia0 += uusia1;
        } else {
            maara += uusia0;
            uusia1 += uusia0;
        }
        if (maara > tavoite) {
            break;
        }
    }
    return maara;
}

int main() {
  ios_base::sync_with_stdio(false);
  ll tavoite;
  cin >> tavoite;

  ll minimi = 1;
  ll maksimi = 28;
  while (minimi != maksimi) {
      ll pituus = ll((minimi + maksimi) / 2);
      ll arvo = 1;
      for (ll i = 0; i < pituus - 1; i++) {
          arvo*=2;
          arvo+=(i%2);
      }
      string jono = bitset<29>(arvo).to_string();
      jono.erase(0, 29 - pituus);
      if (alijonot(jono, tavoite) >= tavoite) {
          maksimi = pituus;
      } else {
          minimi = pituus + 1;
      }
  }
  ll pituus = minimi;
  ll alku = pow(2, pituus - 1);
  ll loppu = 2*alku;
  set<ll> kaytetyt;
  bool parillinen = tavoite % 2 == 0;
  while (true) {
      vector<ll> a;
      int maxj;
      if (parillinen) {
          a.push_back(alku + 1);
          maxj = 1;
      } else {
          a.push_back(alku);
          a.push_back(alku + 2);
          maxj = 2;
      }
      map<ll, bool> maarat;
      maarat[pituus] = pituus < tavoite;
      for (ll maara = pituus - 1; maara < pituus / 2; maara--) {
          vector<ll> patkat;
          ll patkienMaara = pituus - maara + 1;
          ll maara1 = maara;
          while (maara1 > 0) {
              ll patka = maara / patkienMaara;
              patkienMaara--;
              patkat.push_back(patka);
              maara1 -= patka;
          }
          string jono = "";
          while (patkat.size() > 2) {
              for (ll i = 0; i < patkat.front(); i++) {
                  jono += '1';
              }
              jono += '0';
              patkat.erase(patkat.begin());
              for (ll i = 0; i < patkat.back(); i++) {
                  jono += '1';
              }
              jono += '0';
              patkat.pop_back();
          }
          if (patkat.size() == 2) {
              for (ll i = 0; i < patkat.front(); i++) {
                  jono += '1';
              }
              jono += '0';
              patkat.erase(patkat.begin());
          }
          for (ll i = 0; i < patkat.back(); i++) {
              jono += '1';
          }
          maarat[maara] = alijonot(jono, tavoite) < tavoite;
      }
      for (int j = 0; j < maxj; j++) {
          for (ll i = a[j]; i < loppu; i+=3) {
              if (kaytetyt.count(i) != 0) {
                  continue;
              }
              string jono = bitset<30>(i).to_string();
              jono.erase(0, 30 - pituus);
            // if (kaytetyt.count(jono) != 0) {
            //     continue;
            // }
              if (alijonot(jono, tavoite) == tavoite) {
                  cout << jono << endl;
                  return 0;
              }
              if (i % 2 != 0) {
                  reverse(jono.begin(),jono.end());
                  bitset<30> bits;
                  istringstream is(jono);
                  is >> bits;
                  kaytetyt.insert(bits.to_ulong());
              } else {
                  jono = bitset<30>(loppu-1-i).to_string();
                  jono.erase(0, 30-pituus);
                  reverse(jono.begin(),jono.end());
                  bitset<30> bits;
                  istringstream is(jono);
                  is >> bits;
                  kaytetyt.insert(bits.to_ulong());
              }
          }
      }
      alku = loppu;
      loppu *= 2;
      pituus += 1;
  }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1
view   save

correct output
1
view   save

user output
1
view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
2
view   save

correct output
11
view   save

user output
11
view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
3
view   save

correct output
10
view   save

user output
10
view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
4
view   save

correct output
1111
view   save

user output
1111
view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
5
view   save

correct output
110
view   save

user output
100
view   save

Test 6

Group: 1

Verdict: ACCEPTED

input
6
view   save

correct output
101
view   save

user output
101
view   save

Test 7

Group: 1

Verdict: ACCEPTED

input
7
view   save

correct output
1110
view   save

user output
1000
view   save

Test 8

Group: 1

Verdict: ACCEPTED

input
8
view   save

correct output
1100
view   save

user output
1100
view   save

Test 9

Group: 1

Verdict: ACCEPTED

input
9
view   save

correct output
1101
view   save

user output
1011
view   save

Test 10

Group: 1

Verdict: ACCEPTED

input
10
view   save

correct output
1001
view   save

user output
1001
view   save

Test 11

Group: 2

Verdict: ACCEPTED

input
38
view   save

correct output
1101011
view   save

user output
1101011
view   save

Test 12

Group: 2

Verdict: ACCEPTED

input
13
view   save

correct output
11011
view   save

user output
11011
view   save

Test 13

Group: 2

Verdict: ACCEPTED

input
90
view   save

correct output
111001010
view   save

user output
100100010
view   save

Test 14

Group: 2

Verdict: ACCEPTED

input
25
view   save

correct output
110010
view   save

user output
101100
view   save

Test 15

Group: 2

Verdict: ACCEPTED

input
82
view   save

correct output
111001101
view   save

user output
100010011
view   save

Test 16

Group: 2

Verdict: ACCEPTED

input
94
view   save

correct output
1100011110
view   save

user output
1000011100
view   save

Test 17

Group: 2

Verdict: ACCEPTED

input
100
view   save

correct output
1111001001
view   save

user output
1001001111
view   save

Test 18

Group: 2

Verdict: ACCEPTED

input
99
view   save

correct output
110010010
view   save

user output
101001110
view   save

Test 19

Group: 2

Verdict: ACCEPTED

input
98
view   save

correct output
110110010
view   save

user output
100111010
view   save

Test 20

Group: 2

Verdict: ACCEPTED

input
92
view   save

correct output
100110001
view   save

user output
100011001
view   save

Test 21

Group: 3

Verdict: ACCEPTED

input
1666
view   save

correct output
101101100100101
view   save

user output
100100010101010
view   save

Test 22

Group: 3

Verdict: ACCEPTED

input
897
view   save

correct output
11101001101010
view   save

user output
10101001101000
view   save

Test 23

Group: 3

Verdict: ACCEPTED

input
4466
view   save

correct output
111101010110100101
view   save

user output
101001001110001011
view   save

Test 24

Group: 3

Verdict: ACCEPTED

input
4240
view   save

correct output
11011001011010101
view   save

user output
10101011010011011
view   save

Test 25

Group: 3

Verdict: ACCEPTED

input
3089
view   save

correct output
1011001010100101
view   save

user output
1010010101001101
view   save

Test 26

Group: 3

Verdict: ACCEPTED

input
4697
view   save

correct output
11010101101010110
view   save

user output
10010101001010100
view   save

Test 27

Group: 3

Verdict: ACCEPTED

input
4608
view   save

correct output
11010110101001010
view   save

user output
10101101010010100
view   save

Test 28

Group: 3

Verdict: ACCEPTED

input
4625
view   save

correct output
111011001100101001
view   save

user output
100010101110110110
view   save

Test 29

Group: 3

Verdict: ACCEPTED

input
4611
view   save

correct output
11010101010101100
view   save

user output
11010100101001010
view   save

Test 30

Group: 3

Verdict: ACCEPTED

input
4917
view   save

correct output
10110100101010110
view   save

user output
10010101011010010
view   save

Test 31

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
178555
view   save

correct output
1011010110110101010110110
view   save

user output
(no output)
view   save

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
864856
view   save

correct output
10111010110110100100101010010
view   save

user output
(no output)
view   save

Test 33

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
112146
view   save

correct output
1101110101011001100100110
view   save

user output
(no output)
view   save

Test 34

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
741124
view   save

correct output
1011010011010101100101011010
view   save

user output
(no output)
view   save

Test 35

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
511902
view   save

correct output
1011010100011010100101001110
view   save

user output
(no output)
view   save

Test 36

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
920019
view   save

correct output
11100100101101010101001101010
view   save

user output
(no output)
view   save

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
933943
view   save

correct output
10101011010100100110100111001
view   save

user output
(no output)
view   save

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
973410
view   save

correct output
1011010101011010101010101001
view   save

user output
(no output)
view   save

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
954943
view   save

correct output
10110110010011010100100110101
view   save

user output
(no output)
view   save

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
911674
view   save

correct output
1010110010110101010101010110
view   save

user output
(no output)
view   save