General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
30168369 Practice:
skpro19
404C - 32 GNU C++11 Time limit exceeded on test 7 1000 ms 20744 KB 2017-09-07 02:42:02 2017-09-07 02:42:02
 
 
→ Source
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<cctype>
#include <iomanip>
#include <string>
#include <sstream>

#include <functional>
#include <numeric>
#include <stack>
#include <climits>
#include <float.h>
#include<unordered_map>
#include <bitset>


using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=    b;i--)
#define sz(a) ((int)a.size())
#define all(c) c.begin(), c.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define sz(a) ((int)a.size())

//#define fast ios_base::sync_with_stdio(0);cin.tie(0) ; 

typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;

typedef vector<pair<int, int> > vpii;
typedef map<int, int> mii;
typedef map<ll, ll> mll;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef long double ld;


template <class T> const T& max(const T& a, const T&b, const T&c) { return max(a, max(b, c)); }

template <class T> const T& min(const T& a, const T&b, const T&c) { return min(a, min(b, c)); }

void sc(int &a) { scanf("%d", &a); }void sc(ll &a) { scanf("%lld", &a); }void sc(int& a, int& b) { sc(a); sc(b); }
void sc(ll &a, ll &b) { sc(a); sc(b); }void sc(int& a, int& b, int& c) { sc(a, b); sc(c); }void sc(ll& a, ll& b, ll& c) { sc(a, b); sc(c); }
void prl(int a) { printf("%d\n", a); }void prl(ll a) { printf("%lld\n", a); }void prl() { printf("\n"); }
void prs(int a) { printf("%d ", a); }void prs(ll a) { printf("%lld ", a); }


int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

ll poww(ll a, ll b) {

	if (b == 0) return 1;

	ll tmp = poww(a, b / 2);

	return (b & 1 ? a * tmp * tmp : tmp * tmp);

}



ll sumOfDigs(string s) { ll sum = 0; for (int i = 0; i < s.length(); i++) sum += s[i] - '0'; return sum; }

ll sumOfDigs(ll n) { return (n < 10 ? n : n % 10 + sumOfDigs(n / 10)); }

string itos(ll i) { string s = ""; 	while (i) { s += char(i % 10 + '0'); i /= 10; } reverse(all(s));  return s; }

ll stoi(string &s) { ll tot = 0; for (int i = (int)s.length() - 1, j = 1; i >= 0; i--, j *= 10) { tot += j * (s[i] + '0'); }  return tot; }


int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };


using namespace std;

#define PI acos((ld)-1.0) 





// printf("%.8lf\n", sum * 1.0 / n);  // precision setting


ll mod = 1e9 + 7;

void tt() {

#ifndef online	_judge
	freopen("test.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

#endif
}

ll modpower(ll x, ll y, ll p)
{

	x %= mod;

	if (!y) return 1;

	ll res = 1;

	if (y & 1) { res *= x;  res %= p; }

	ll z = modpower(x, y / 2, p);

	z %= p;

	z *= z;

	z %= mod;

	res *= z;

	res %= p;

	return res;

}

pii a[1000 * 1000 + 10];


vector<int> mpp[1000 * 1000 + 10]; 

vector<pii> ans;

int n, k;

int len, start;

void dfs(int curr) {

	if (len >= n) { return;  }

	if ((int)mpp[len].size() == 0 && (int)mpp[len + 1].size() != 0) {   cout << -1 << endl; exit(0); }

	//cout << "HI" << endl; 

	for (int i = 1; i <= k - 1 + (curr == start); i++) {
		if ((int)mpp[len].size()) {

			ans.pb({ curr, mpp[len].back() });
			len++;
			dfs(mpp[len - 1].back());
			len--;
			mpp[len].pop_back();

		}
	}
}

int main() {

	
	//stt();
	fast;
	cin >> n >> k;

	start = -1;

	for (int i = 1; i <= n; i++) {

		int x;
		cin >> x;
		mpp[x].pb(i);
		if (x == 0) start = i;

	}


	if ((int)mpp[0].size() != 1) { return cout << -1 << endl, 0; }

	
	len++;

	dfs(start);

	mpp[0].clear(); 
	
	
	for (auto t : mpp) if ((int)t.size()) { return cout << -1 << endl, 0; }
	cout << (int)ans.size() << endl;
	for (auto t : ans)cout << t.ff << " " << t.ss << endl;
 
	return 0;

}
 
 
1
Time: 15 ms, memory: 19572 KB
Verdict: OK
Input
3 2
0 1 1
Participant's output
2
1 3
1 2
Jury's answer
2
1 2
1 3
Checker comment
ok ok. The answer exists.
 
 
2
Time: 15 ms, memory: 19572 KB
Verdict: OK
Input
4 2
2 0 1 3
Participant's output
3
2 3
3 1
1 4
Jury's answer
3
1 3
1 4
2 3
Checker comment
ok ok. The answer exists.
 
 
3
Time: 15 ms, memory: 19568 KB
Verdict: OK
Input
3 1
0 0 0
Participant's output
-1
Jury's answer
-1
Checker comment
ok No answer.
 
 
4
Time: 15 ms, memory: 19568 KB
Verdict: OK
Input
5 3
0 2 1 2 1
Participant's output
4
1 5
5 4
5 2
1 3
Jury's answer
4
1 3
1 5
2 5
4 5
Checker comment
ok ok. The answer exists.
 
 
5
Time: 15 ms, memory: 19572 KB
Verdict: OK
Input
7 3
2 2 0 1 3 2 1
Participant's output
6
3 7
7 6
6 5
7 2
3 4
4 1
Jury's answer
6
1 7
2 7
3 4
3 7
4 6
5 6
Checker comment
ok ok. The answer exists.
 
 
6
Time: 15 ms, memory: 19572 KB
Verdict: OK
Input
9 4
2 1 1 3 1 2 2 1 0
Participant's output
8
9 8
8 7
7 4
8 6
8 1
9 5
9 3
9 2
Jury's answer
8
1 8
2 9
3 9
4 7
5 9
6 8
7 8
8 9
Checker comment
ok ok. The answer exists.
 
 
7
Time: 1000 ms, memory: 20744 KB
Verdict: TIME_LIMIT_EXCEEDED
Input
100000 59094
22 24 21 22 21 24 17 16 17 25 21 26 18 18 23 23 25 17 19 28 14 19 17 23 27 22 21 26 20 18 21 22 21 23 21 18 23 17 21 20 17 20 17 13 23 24 18 18 22 23 22 11 27 20 19 17 19 19 20 20 22 21 15 15 15 22 21 24 22 21 21 18 22 24 21 21 20 21 22 18 20 12 18 20 18 18 20 23 21 21 26 22 18 21 19 21 21 23 19 19 19 20 17 19 21 16 28 26 15 14 23 20 17 19 25 17 20 22 25 22 13 23 23 19 18 21 20 11 22 16 25 20 22 23 25 20 17 22 15 25 17 20 22 8 27 19 23 17 18 23 16 18 20 19 22 22 18 24 19 21 14 21 16 15 22 20 ...
Participant's output
Jury's answer
Checker comment