社区讨论
橙题变蓝题(一个笑话,求助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)
(我只研究出来第一份代码的 hack,即 n <=10 时,
回复
共 5 条回复,欢迎继续交流。
正在加载回复...