oj.uz

Submission #107663

# Submission time Handle Problem Language Result Execution time Memory
107663 2019-04-25T12:13:53 Z patrikpavic2 Sequence (BOI14_sequence) C++17
34 / 100
 319 ms 888 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <map>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef set < int > si;

const int N = 1e5 + 500;
const int M = 1e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int OFF = (1 << 18);
const int LOG = 20;
const double EPS = 1e-9;
const double PI = 3.1415926535;

int n, x, a[N], tr[N];
ll fin = (ll)INF * INF;

bool inside(int i,int k){
    for(;k;k /= 10)
        if(k % 10 == i && k != 0) return 1;
    return 0;
}

vector < int > v;

int main(){
    scanf("%d", &n);
    if(n <= 1000){
        for(int i = 0;i < n;i++) scanf("%d", a + i);
        for(int st = 1;st < 10000;st++){
            memset(tr, 0, sizeof(tr));
            int bad = 0;
            for(int i = 0;i < n;i++){
                if(!inside(a[i], st + i)) bad = 1, tr[a[i]] = 1;
            }

            ll ans = st, pot = 10000LL;
            //printf("ANS %lld POT %lld\n", ans, pot);
            for(int i = 9;i >= 1;i--){
                //printf("%d", tr[i]);
                if(tr[i]){
                    ans += i * pot;
                    pot *= 10LL;
                }
            }
            //printf("\nST: %d\n", st);
            pot /= 10LL;
            if(tr[0]) {
                if(pot == 1000LL)
                    ans += 100000LL;
                else
                    ans = ans % pot + (ans - ans % pot) * 10LL;
            }
            //printf("%lld\n", ans);
            //char c; scanf("%c", &c);
            fin = min(fin, ans);
        }
        printf("%lld\n", fin);
        return 0;
    }
    scanf("%d", &x);
    if(x == 0){
        int pot = 1;
        while(pot - (pot / 10 * 9) - 1 < n){
            pot = 10 * pot + 1;
        }
        printf("%d\n", (pot / 10 * 9) + 1);
        return 0;
    }
    if(x == 9){
        int pot = 1, pot2 = 1;
        while(pot2 - (pot / 10 * 8) - 1 < n){
            pot = 10 * pot + 1;
            pot2 = 10 * pot2;
        }
        printf("%d\n", (pot / 10 * 8) + 1);
        return 0;
    }
    printf("%d", x);
    for(int i = 1;i < n;i *= 10) printf("0");
    printf("\n");
    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:49:17: warning: variable 'bad' set but not used [-Wunused-but-set-variable]
             int bad = 0;
                 ^~~
sequence.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
sequence.cpp:46:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i = 0;i < n;i++) scanf("%d", a + i);
                                  ~~~~~^~~~~~~~~~~~~
sequence.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
     ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 728 KB Output is correct
2 Correct 221 ms 860 KB Output is correct
3 Correct 187 ms 768 KB Output is correct
4 Correct 210 ms 732 KB Output is correct
5 Correct 191 ms 740 KB Output is correct
6 Correct 209 ms 760 KB Output is correct
7 Correct 228 ms 740 KB Output is correct
8 Correct 276 ms 760 KB Output is correct
9 Correct 204 ms 768 KB Output is correct
10 Correct 295 ms 732 KB Output is correct
11 Correct 282 ms 768 KB Output is correct
12 Correct 185 ms 768 KB Output is correct
13 Correct 194 ms 768 KB Output is correct
14 Correct 316 ms 640 KB Output is correct
15 Correct 299 ms 744 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 640 KB Output is correct
2 Correct 224 ms 736 KB Output is correct
3 Correct 197 ms 888 KB Output is correct
4 Correct 190 ms 768 KB Output is correct
5 Correct 179 ms 888 KB Output is correct
6 Correct 190 ms 796 KB Output is correct
7 Correct 276 ms 888 KB Output is correct
8 Correct 188 ms 768 KB Output is correct
9 Correct 235 ms 640 KB Output is correct
10 Correct 184 ms 640 KB Output is correct
11 Correct 261 ms 740 KB Output is correct
12 Correct 255 ms 760 KB Output is correct
13 Correct 245 ms 640 KB Output is correct
14 Correct 222 ms 768 KB Output is correct
15 Correct 209 ms 768 KB Output is correct
16 Correct 319 ms 760 KB Output is correct
17 Correct 305 ms 768 KB Output is correct
18 Correct 202 ms 760 KB Output is correct
19 Correct 248 ms 860 KB Output is correct
20 Incorrect 302 ms 768 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 888 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 256 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 768 KB Output is correct
2 Correct 222 ms 636 KB Output is correct
3 Correct 204 ms 760 KB Output is correct
4 Correct 185 ms 760 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -