Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define forn(i,a,b) for( int i = (a); i < (b); i++ )
- #define rep(i,n) forn(i,0,n)
- #define repe(i,n) for( i = 0; i < (n); i++ )
- #define fi first
- #define se second
- #define mp make_pair
- #define pb push_back
- #define pii pair<int,int>
- #define pll pair<ll,ll>
- #define pdd pair<double,double>
- const int MXP = 19;
- const int MXN = 100100;
- vector< pair<ll,int> > val [MXP];
- int ans [MXN];
- int anc;
- int main()
- {
- //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- freopen("exact.in", "r", stdin); freopen("exact.out", "w", stdout);
- ll x;
- int n;
- scanf("%lld%d", &x, &n);
- rep(i,n){
- int k,q;
- scanf("%d%d", &k, &q);
- ll cur = pow(10,k) * q;
- val[k].pb( {cur,i} );
- }
- rep(i,MXP) sort(val[i].begin(), val[i].end());
- ll rest = 0;
- ull cpow = 1;
- vector< pair<ll,int> > tmp;
- vector< pair<ll,int> > poss;
- int curp = -1;
- while(x){
- curp++;
- cpow*=10;
- tmp.clear();
- tmp.resize( poss.size() + val[curp].size() );
- merge(poss.begin(), poss.end(), val[curp].begin(), val[curp].end(), tmp.begin());
- tmp.swap(poss);
- ll cur = x%cpow;
- x -= cur;
- if(rest>=cur){
- rest -= cur;
- continue;
- }
- cur -= (rest/(cpow/10)) * (cpow/10);
- while(!poss.empty()){
- pair<ll,int> q = poss.back();
- ans[anc++] = q.se;
- poss.pop_back();
- if(cur <= q.fi){
- rest += q.fi - cur;
- cur = 0;
- break;
- }
- else{
- cur -= q.fi;
- }
- }
- if(cur<=rest){
- rest -= cur;
- }
- else{
- printf("-1");
- return 0;
- }
- }
- printf("%d\n", anc);
- rep(i,anc) printf("%d ", ans[i]+1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement