oj.uz

Submission #67936

# Submission time Handle Problem Language Result Execution time Memory
67936 2018-08-15T14:51:51 Z yusufake Binary Subsequences (info1cup17_binary) C++
100 / 100
 718 ms 576 KB 
#include<bits/stdc++.h> 
using namespace std; 

#define pb push_back
#define mp make_pair
#define st first
#define nd second

typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 2e6 + 6; 

pair < int , pp > ans;

int f(int x, int y){
    if(x < y) swap(x,y); 
    int a=x; int b=y;
    int t;
    int zz=0;
    for(; y ;){
        t = x%y;
        zz += x/y;
        x = y;
        y = t;
    }
    if(x==1)
        ans = min(ans , mp(zz,mp(a,b)));
    return x == 1;
}

int ww,k,t,i,x,y,zz,h;
int main(){
    scanf("%d",&ww);
    for(;ww--; puts("")){
        scanf("%d",&k);
        k += 2;
        t = 0;
        ans.st = mod;
        zz = k/2;
        for(i=1;i<=zz;i++){
            t += 2*f(i,k-i);
        }
        if(k%2==0) t -= f(zz,zz);
        printf("%d\n",t);
        x = ans.nd.st;
        y = ans.nd.nd;
        for(; y ; h=!h){
        t = x%y;
        zz = x/y;
        if(!t) zz--;
        for(;zz--;) printf("%d ",h);
        x = y;
        y = t;
    }
    
    }
    return 0;
}

Compilation message

binary.cpp: In function 'int main()':
binary.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ww);
     ~~~~~^~~~~~~~~~
binary.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~

Subtask #1
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 504 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 504 KB Output is correct
2 Correct 58 ms 504 KB Output is correct
3 Correct 61 ms 504 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 576 KB Output is correct
2 Correct 718 ms 576 KB Output is correct
3 Correct 663 ms 576 KB Output is correct