Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#343#5. 「WyOJ Round 1」炽 · 踏浪而歌WXZY104ms5500kbC++232.2kb2025-04-19 18:54:092025-04-19 18:54:11

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define lson 2*p
#define rson 2*p+1
#define x first
#define y second
#define LL long long
#define lowbit(x) x&-x
// #define endl "\n"
const int N=1e6+10;
const int mod=1e9+7;
int a[N],cnt[N];
void solve() {
	int n;
	cin>>n;
	priority_queue<PII> q;
	int sum=0;
	set<int> pos;
	set<PII> st;
	vector<PII> ans;
	int maxn=0;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		sum+=a[i];
		maxn=max(maxn,a[i]);
		cnt[a[i]]++;
		if(!a[i]) continue;;
		pos.insert(i);
		st.insert({a[i],-i});
	}
	if(sum&1) {
		if(maxn*2>sum) {
			for(int i=1;i<=n;i++) {
				if(a[i]==maxn) {
					ans.push_back({i,i});
					cnt[maxn]--;
					cnt[maxn-1]++;
					a[i]--;
					if(!a[i]) pos.erase(i);
					while(!cnt[maxn]) maxn--;
					break;
				}
			}
		} else {
			for(int i=1;i<=n;i++) {
				if(!a[i]) continue;
				ans.push_back({i,i});
				cnt[a[i]]--;
				cnt[a[i]-1]++;
				a[i]--;
				if(!a[i]) pos.erase(i);
				while(!cnt[maxn]) maxn--;
				break;
			}
		}
		sum--;
	}
	while(maxn*2<sum) {
		int x=*pos.begin();
		pos.erase(x);
		int y=*pos.begin();
		pos.erase(y);
 		cnt[a[x]]--,cnt[a[y]]--;
		st.erase({a[x],-x});
		st.erase({a[y],-y});
		a[x]--,a[y]--;
		if(a[x]) st.insert({a[x],-x});
		if(a[y]) st.insert({a[y],-y});
		cnt[a[x]]++,cnt[a[y]]++;
		ans.push_back({x,y});
		while(!cnt[maxn]) maxn--;
		sum-=2;
		if(a[x]) pos.insert(x);
		if(a[y]) pos.insert(y);
	}
	while(maxn*2>sum) {
		auto [x,y]=*st.rbegin();
		ans.push_back({-y,-y});
		y=-y;
		st.erase({a[y],-y});
		cnt[a[y]]--;
		cnt[a[y]-1]++;
		a[y]--;
		sum--;
		while(!cnt[maxn]) maxn--;
		if(a[y]) st.insert({a[y],-y});
		if(!a[y]) pos.erase(y);
	}
	auto [x,y]=*st.rbegin();
	y=-y;
	pos.erase(y);
	while(pos.size()) {
		if(!pos.size()) break;
		int x=*pos.begin();
		ans.push_back({min(x,y),max(x,y)});
		a[x]--,a[y]--;
		if(!a[x]) pos.erase(x);
	}
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for(auto [u,v]:ans) cout<<u<<" "<<v<<endl;
}
signed main() {
    int T=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // cin>>T;
    while(T--) {    
        solve();
    }
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 4ms
memory: 5500kb

input:

6
3 4 1 2 4 6

output:

10
1 2
1 2
1 2
2 3
4 6
4 6
5 6
5 6
5 6
5 6

result:

ok 21 numbers

Test #2:

score: 0
Time Limit Exceeded

input:

1000
1000 1000 1000 999 996 993 991 991 991 991 991 991 988 988 988 988 987 984 980 980 978 978 977 ...

output:

259561
1 1
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1...

result:


Test #3:

score: 0
Time Limit Exceeded

input:

5
93761 154479 466694 134030 151036

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1...

result:


Test #4:

score: 0
Time Limit Exceeded

input:

56700
20 9 3 26 6 14 11 26 15 4 7 7 18 3 55 16 0 2 71 8 21 3 15 21 2 25 38 10 2 15 3 1 3 15 6 2 26 5...

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 3
1 3
1 3
1 4
1 4
1 4
1 4
1 4
1 4
1 4
1 4
4 5
4 5
4 5
4...

result:


Test #5:

score: 0
Time Limit Exceeded

input:

18574
19 245 80 2 53 157 18 27 35 19 109 14 30 97 26 10 5 22 142 102 13 114 67 70 142 131 10 177 18 ...

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
2...

result:


Test #6:

score: 0
Time Limit Exceeded

input:

36045
6 62 19 5 21 38 42 13 52 3 10 4 14 65 24 15 9 21 19 24 1 3 2 59 2 19 80 28 9 39 49 26 20 20 14...

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2...

result:


Test #7:

score: 0
Time Limit Exceeded

input:

100
442 37503 827 703 10394 1215 23599 313 1705 10819 6152 89 341 3448 778 7153 20397 5166 2735 2100...

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1...

result:


Test #8:

score: 0
Time Limit Exceeded

input:

1000
6 436 820 182 327 3272 993 1042 321 2717 69 4321 706 4565 1280 528 1632 1317 916 125 262 1712 6...

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2...

result:


Test #9:

score: 0
Time Limit Exceeded

input:

10000
6 107 38 107 3 28 89 15 30 19 89 2 435 75 45 55 119 125 15 42 101 83 9 134 3 278 292 55 255 2 ...

output:

500000
1 2
1 2
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2...

result:


Test #10:

score: 0
Time Limit Exceeded

input:

100000
3 3 62 19 5 21 0 17 21 2 1 36 3 11 2 3 10 22 17 3 10 0 4 3 11 20 11 22 12 12 12 1 10 4 9 6 4 ...

output:

500000
1 2
1 2
1 2
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 4
3 5
3...

result: