Submission #1744997


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <fstream>

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <numeric>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
// #include <unordered_map>
#include <set>
#include <utility>
#include <bitset>
#include <limits>
#include <climits>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

int solve(int K) {
    priority_queue<ii> pq;

    vector<int> vis(K, 0);

    pq.push(ii(-1, 1));
    while (!pq.empty()) {
        ii p = pq.top(); pq.pop();
        int cnt = -p.first, curr = p.second;
        if (curr == 0) return cnt;

        vis[curr] = 1;
        int next = (curr + 1)% K;
        if (vis[next] == 0)
            pq.push(ii(-(cnt+1), next));

        next = (curr * 10) % K;
        if (vis[next] == 0)
            pq.push(ii(-cnt, next));
    }
}

int main() {

    int K; cin >> K;

    cout << solve(K) << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Small Multiple
User naoya_t
Language C++14 (Clang 3.8.0)
Score 700
Code Size 2063 Byte
Status
Exec Time 1169 ms
Memory 9324 KB

Compile Error

./Main.cpp:81:1: warning: control may reach end of non-void function [-Wreturn-type]
}
^
1 warning generated.

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 700 / 700 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 5 ms 888 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 1 ms 256 KB
09.txt 1 ms 256 KB
10.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 1 ms 256 KB
16.txt 1 ms 256 KB
17.txt 1 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 256 KB
21.txt 1 ms 640 KB
22.txt 155 ms 1784 KB
23.txt 14 ms 1276 KB
24.txt 19 ms 1276 KB
25.txt 21 ms 1276 KB
26.txt 7 ms 1024 KB
27.txt 16 ms 1276 KB
28.txt 17 ms 1276 KB
29.txt 12 ms 1024 KB
30.txt 20 ms 1276 KB
31.txt 1 ms 256 KB
32.txt 1 ms 256 KB
33.txt 14 ms 1148 KB
34.txt 5 ms 640 KB
35.txt 13 ms 896 KB
36.txt 6 ms 1024 KB
37.txt 5 ms 512 KB
38.txt 4 ms 512 KB
39.txt 8 ms 896 KB
40.txt 2 ms 384 KB
41.txt 10 ms 1024 KB
42.txt 27 ms 1276 KB
43.txt 3 ms 384 KB
44.txt 2 ms 256 KB
45.txt 10 ms 768 KB
46.txt 13 ms 896 KB
47.txt 6 ms 512 KB
48.txt 70 ms 2804 KB
49.txt 18 ms 1024 KB
50.txt 12 ms 768 KB
51.txt 5 ms 512 KB
52.txt 9 ms 640 KB
53.txt 24 ms 896 KB
54.txt 13 ms 768 KB
55.txt 14 ms 896 KB
56.txt 21 ms 896 KB
57.txt 45 ms 1276 KB
58.txt 152 ms 1656 KB
59.txt 214 ms 2804 KB
60.txt 290 ms 2676 KB
61.txt 59 ms 512 KB
62.txt 73 ms 1148 KB
63.txt 74 ms 1276 KB
64.txt 155 ms 1784 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1169 ms 9324 KB