社区讨论

橙题变蓝题(一个笑话,求助QAQ

P14958「KWOI R1」Permutation Problem参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mk8ek5jb
此快照首次捕获于
2026/01/10 22:30
上个月
此快照最后确认于
2026/01/14 15:15
上个月
查看原帖
赛时脑子抽筋,写了两份代码(每一份都是黄色级别的),一份过了 subtask1、2,另一份过了 subtask3、4、5,于是将两份合起来就 A 了:
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
#define int long long

template <typename T> void read(T &x){
	x=0;char c;int f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
	x*=f;
}

inline void write(int x,char ch){
	if(!x){putchar(48),putchar(ch);return;}
	if(x<0)putchar(45),x=-x;
	char a[40];
	int i=0;
	while(x)a[++i]=x%10+48,x/=10;
	while(i)putchar(a[i--]);
	putchar(ch);
}
unordered_map<int,int> freq;
int n,ans[N];
unordered_map<int,multiset<int>> available_for_val;
unordered_set<int> used_products;
int check[N];
unordered_set<int> vis;
set<int> avail;
vector<pair<int,int>> arr;
signed main(){
	read(n);
	if (n<=10){//第一份代码
		for(int i=1;i<=n;i++){
			int x;
			read(x);
			arr.push_back({x, i});
		}
		for(int b=1;b<=n;b++){
			for(auto &p : arr){
				available_for_val[p.first].insert(b);
			}
		}
	
		
		for(auto &p : arr) freq[p.first]++;
		
		sort(arr.begin(), arr.end(), [&](const pair<int,int> &x, const pair<int,int> &y){
			if(freq[x.first] != freq[y.first])
				return freq[x.first] > freq[y.first];
			return x.first < y.first; 
		});
		
		for(auto &p : arr){
			int val = p.first;
			int idx = p.second;
			
			if(available_for_val[val].empty()){
				write(-1,'\n');
				return 0;
			}
			bool found = false;
			for(auto it = available_for_val[val].begin(); it != available_for_val[val].end(); ++it){
				int b_val = *it;
				long long product = 1LL * val * b_val;
				
				if(used_products.find(product) == used_products.end()){
					ans[idx] = b_val;
					used_products.insert(product);
					for(auto &g : available_for_val){
						g.second.erase(b_val);
					}
					
					found = true;
					break;
				}
			}
			
			if(!found){
				write(-1,'\n');
				return 0;
			}
		}
		for(int i=1;i<=n;i++){
			write(ans[i], i==n?'\n':' ');
		}
		return 0;
    }
  //第二份代码
	for (int i=1;i<=n;i++)avail.insert(i);
	for (int i=1,val;i<=n;i++){
		read(val);
		bool flag=false;
		for (auto it=avail.begin();it!=avail.end();++it){
			int cur=1LL*val*(*it);
			if (vis.find(cur)==vis.end()){
				ans[i]=*it;
				vis.insert(cur);
				avail.erase(it);
				flag=true;
				break;
			}
		}
		if (!flag){
			write(-1,'\n');
			return 0;
		}
	}
	for (int i=1;i<=n;i++)write(ans[i],' ');
	return 0;
}
其实该代码为错误❌的,有兴趣的可以自己研究一下hack。
(我只研究出来第一份代码的 hack,即 n <=10 时,求第二份 hack)

回复

5 条回复,欢迎继续交流。

正在加载回复...