oj.uz

Submission #107668

# Submission time Handle Problem Language Result Execution time Memory
107668 2019-04-25T12:17:39 Z patrikpavic2 Sequence (BOI14_sequence) C++17
34 / 100
 365 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 = 0;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, lst = -1;
            //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;
                    lst = i * pot;
                    pot *= 10LL;
                }
            }
            //printf("\nST: %d\n", st);
            if(tr[0]) {
                if(lst != -1)
                    ans += 9 * lst;
                else
                    ans += 100000LL;
            }
            //printf("%lld\n", ans);
            //char c; scanf("%c", &c);
            if(ans) 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 219 ms 860 KB Output is correct
2 Correct 222 ms 888 KB Output is correct
3 Correct 202 ms 764 KB Output is correct
4 Correct 206 ms 760 KB Output is correct
5 Correct 191 ms 888 KB Output is correct
6 Correct 266 ms 760 KB Output is correct
7 Correct 267 ms 768 KB Output is correct
8 Correct 273 ms 888 KB Output is correct
9 Correct 186 ms 760 KB Output is correct
10 Correct 287 ms 640 KB Output is correct
11 Correct 279 ms 640 KB Output is correct
12 Correct 203 ms 760 KB Output is correct
13 Correct 218 ms 640 KB Output is correct
14 Correct 312 ms 732 KB Output is correct
15 Correct 314 ms 760 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 640 KB Output is correct
2 Correct 225 ms 760 KB Output is correct
3 Correct 212 ms 760 KB Output is correct
4 Correct 228 ms 860 KB Output is correct
5 Correct 201 ms 760 KB Output is correct
6 Correct 194 ms 764 KB Output is correct
7 Correct 365 ms 640 KB Output is correct
8 Correct 188 ms 760 KB Output is correct
9 Correct 259 ms 744 KB Output is correct
10 Correct 186 ms 760 KB Output is correct
11 Correct 294 ms 768 KB Output is correct
12 Correct 335 ms 640 KB Output is correct
13 Correct 281 ms 760 KB Output is correct
14 Correct 202 ms 768 KB Output is correct
15 Correct 194 ms 768 KB Output is correct
16 Correct 292 ms 764 KB Output is correct
17 Correct 312 ms 760 KB Output is correct
18 Correct 217 ms 760 KB Output is correct
19 Correct 223 ms 860 KB Output is correct
20 Incorrect 285 ms 860 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 183 ms 768 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 732 KB Output is correct
2 Correct 242 ms 888 KB Output is correct
3 Correct 211 ms 888 KB Output is correct
4 Correct 204 ms 768 KB Output is correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Halted 0 ms 0 KB -