QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#442589 | #8529. Balance of Permutation | ucup-team3699# | Compile Error | / | / | C++23 | 2.8kb | 2024-06-15 12:54:44 | 2024-06-15 12:54:44 |
Judging History
answer
//#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
const int mol=998244353;
void add(int &t1, int t2){
t1+=t2;
if(t1>=mol) t1-=mol;
}
int dp[35][35][2005], ans[33];
bool us[35], ov[35];
//i was pick on id-, i will pick id+, sum
void solve(){
int n, b;string k;
cin>>n>>b;cin>>k;
__int128 kk=0;
for(auto jj: k) kk*=10, kk+=jj-'0';
dp[0][0][n*n]=1;
int cost=n*n;
int tot=0, p=cost;
for(int pos=1;pos<=n;pos++){
for(int num=1;num<=n;num++){
if(us[num]) continue;
ans[pos]=num;
for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) for(int l=0;l<=n*n*2;l++) dp[i][j][l]=0;
dp[0][0][n*n]=1;
for(int i=1;i<=n;i++) ov[i]=0;
pos=3;num=5;
ans[1]=1, ans[2]=2, ans[3]=5;
us[1]=1, us[2]=1;
// for(int i=1;i<=4;i++) us[i]=1;num=4;
// us[3]=0;
for(int i=1;i<=n;i++){
ov[ans[i]]=1;
for(int j=0;j<i;j++){
for(int l=0;l<=n*n*2;l++){
int g=dp[i-1][j][l];
if((us[i]||i==num)&&i<=pos){
if(i==ans[i])
add(dp[i][j][l], g);
else{
if(ov[i]&&ans[i]>i) if(j) add(dp[i][j][l], g);
if(ov[i]&&ans[i]<i) if(j) add(dp[i][j-1][l+i*2], g);
if(!ov[i]&&ans[i]>i) if(l>=i*2) add(dp[i][j+1][l-i*2], g);
if(!ov[i]&&ans[i]<i) if(j) add(dp[i][j][l], g);
}
}
else if(i<=pos){
if(ans[i]>i){
// if(j) add(dp[i][j][l], g); //pick big and pick j
if(l>=i*2) add(dp[i][j+1][l-i*2], g); //pick big and pick i+
}
else if(ans[i]==i)
add(dp[i][j][l], g);
else{
// if(j) add(dp[i][j-1][l+i*2], g); //pick small and pick j
if(j) add(dp[i][j][l], g); //pick small and pick i+
}
}
else if((us[i]||i==num)){
if(ov[i]){
if(j) add(dp[i][j-1][l+i*2], g); //pick small and pick j
if(j) add(dp[i][j][l], g); //pick big and pick j
}
else{
if(j) add(dp[i][j][l], g); //pick small and pick i+
if(l>=i*2) add(dp[i][j+1][l-i*2], g); //pick big and pick i+
}
}
else{
add(dp[i][j][l], g);
if(j) add(dp[i][j-1][l+i*2], g); //pick small and pick j
if(j) add(dp[i][j][l], g); //pick small and pick i+
if(j) add(dp[i][j][l], g); //pick big and pick j
if(l>=i*2) add(dp[i][j+1][l-i*2], g); //pick big and pick i+
}
}
}
}
if(pos==3&&num==5)
cout<<dp[n][0][n*n+b]<<" "<<tot<<"\n";
return;
// return;
if(tot+dp[n][0][n*n+b]>=kk) {
us[num]=1;
cost+=abs(num-pos);
break;
}
tot+=dp[n][0][n*n+b];
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);
// int t;
// cin>>t;
// while(t--)
solve();
return 0;
}
Details
answer.code: In function ‘void solve()’: answer.code:21:18: error: ‘string’ was not declared in this scope 21 | int n, b;string k; | ^~~~~~ answer.code:1:1: note: ‘std::string’ is defined in header ‘<string>’; did you forget to ‘#include <string>’? +++ |+#include <string> 1 | //#include<bits/stdc++.h> answer.code:22:9: error: ‘cin’ was not declared in this scope 22 | cin>>n>>b;cin>>k; | ^~~ answer.code:1:1: note: ‘std::cin’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’? +++ |+#include <iostream> 1 | //#include<bits/stdc++.h> answer.code:22:24: error: ‘k’ was not declared in this scope 22 | cin>>n>>b;cin>>k; | ^ answer.code:92:25: error: ‘cout’ was not declared in this scope 92 | cout<<dp[n][0][n*n+b]<<" "<<tot<<"\n"; | ^~~~ answer.code:92:25: note: ‘std::cout’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’? answer.code:97:39: error: ‘abs’ was not declared in this scope; did you mean ‘ans’? 97 | cost+=abs(num-pos); | ^~~ | ans answer.code:103:31: error: ‘cout’ was not declared in this scope 103 | for(int i=1;i<=n;i++) cout<<ans[i]<<" "; | ^~~~ answer.code:103:31: note: ‘std::cout’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’? answer.code: In function ‘int main()’: answer.code:107:5: error: ‘ios’ has not been declared 107 | ios::sync_with_stdio(0);cin.tie(0); | ^~~ answer.code:107:29: error: ‘cin’ was not declared in this scope 107 | ios::sync_with_stdio(0);cin.tie(0); | ^~~ answer.code:107:29: note: ‘std::cin’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’?