oj.uz

Submission #156231

# Submission time Handle Problem Language Result Execution time Memory
156231 2019-10-04T15:40:46 Z nikolapesic2802 Sequence (BOI14_sequence) C++14
34 / 100
 154 ms 1264 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}

ll sol=INT_MAX;
vector<ll> pwr;
void gen(vector<int> req,int digit,ll trsol,bool nula)
{
    bool done=1;
    for(auto p:req)
        if(p!=0)
            done=0;
    if(done)
    {
        if(nula)
            trsol+=pwr[digit];
        sol=min(sol,trsol);
        return;
    }
    if(digit>5)
        return;
    int n=req.size();
    for(int y=0;y<10;y++)
    {
        vector<int> sl;
        if(y)
            sl.pb(0);
        int tr=y;
        bool nulaffs=0;
        if(y==0&&(req[0]&1))
            nulaffs=1;
        for(auto p:req)
        {
            if(tr==0)
                sl.pb(0);
            sl.back()|=p&(~(1<<tr));
            tr=(tr+1)%10;
        }
        gen(sl,digit+1,trsol+pwr[digit]*y,nulaffs);
    }
}
int main()
{
	pwr.pb(1);
	for(int i=0;i<10;i++)
        pwr.pb(pwr.back()*10);
    int n,a;
    scanf("%i",&n);
    vector<int> req;
    for(int i=0;i<n;i++)
        scanf("%i",&a),req.pb(1<<a);
    gen(req,0,0,0);
    printf("%i\n",sol);
    return 0;
}

Compilation message

sequence.cpp: In function 'void gen(std::vector<int>, int, long long int, bool)':
sequence.cpp:44:9: warning: unused variable 'n' [-Wunused-variable]
     int n=req.size();
         ^
sequence.cpp: In function 'int main()':
sequence.cpp:75:22: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%i\n",sol);
                      ^
sequence.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
sequence.cpp:73:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&a),req.pb(1<<a);
         ~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 376 KB Output is correct
2 Correct 106 ms 476 KB Output is correct
3 Correct 105 ms 256 KB Output is correct
4 Correct 106 ms 376 KB Output is correct
5 Correct 105 ms 504 KB Output is correct
6 Correct 95 ms 376 KB Output is correct
7 Correct 101 ms 476 KB Output is correct
8 Correct 104 ms 256 KB Output is correct
9 Correct 64 ms 376 KB Output is correct
10 Correct 107 ms 376 KB Output is correct
11 Correct 106 ms 376 KB Output is correct
12 Correct 106 ms 356 KB Output is correct
13 Correct 106 ms 504 KB Output is correct
14 Correct 106 ms 476 KB Output is correct
15 Correct 106 ms 404 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 376 KB Output is correct
2 Correct 106 ms 476 KB Output is correct
3 Correct 104 ms 256 KB Output is correct
4 Correct 106 ms 376 KB Output is correct
5 Correct 105 ms 376 KB Output is correct
6 Correct 96 ms 256 KB Output is correct
7 Correct 102 ms 376 KB Output is correct
8 Correct 100 ms 256 KB Output is correct
9 Correct 105 ms 368 KB Output is correct
10 Correct 64 ms 256 KB Output is correct
11 Incorrect 107 ms 376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 376 KB Output is correct
2 Correct 113 ms 468 KB Output is correct
3 Correct 112 ms 376 KB Output is correct
4 Correct 112 ms 468 KB Output is correct
5 Correct 112 ms 376 KB Output is correct
6 Correct 110 ms 504 KB Output is correct
7 Correct 140 ms 1012 KB Output is correct
8 Correct 128 ms 900 KB Output is correct
9 Correct 153 ms 1264 KB Output is correct
10 Correct 154 ms 1264 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 360 KB Output is correct
2 Correct 106 ms 256 KB Output is correct
3 Correct 105 ms 364 KB Output is correct
4 Correct 106 ms 376 KB Output is correct
5 Incorrect 127 ms 856 KB Output isn't correct
6 Halted 0 ms 0 KB -