| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 543522 | neki | 앵무새 (IOI11_parrots) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define par pair<ll, ll>
#define ld long double
#define mod 998244353
bool addb(bool b1, bool b2, bool& carry){
bool ret = b1 ^ b2 ^ carry;
carry= (b1 && carry) || (b2 && carry) || (b1 && b2);
return ret;
}
bool subb(bool b1, bool b2, bool& carry){
bool ret = b1 ^ b2 ^ carry;
carry=(!b1 && carry) || (!b1 && b2) || (b1 && b2 && carry);
return ret;
}
struct int512{
bitset<512> arr;
int512(){}
int512(int n){arr=bitset<512> (n);}
int512(int n, int m[]){
loop(i, 0, n) loop(j, 0, 8) arr[i * 8+j]=((m[i] & (1<<j))>0);
}
int512 operator+(const int512& oth){
int512 ret;
bool carry=false;
loop(i, 0, 512) ret.arr[i]=addb(arr[i], oth.arr[i], carry);
return ret;
}
int512 operator-(const int512& oth){
int512 ret;
bool carry=false;
loop(i, 0, 512) ret.arr[i]=subb(arr[i], oth.arr[i], carry);
return ret;
}
bool operator<(const int512& oth){
pool(i, 512, 0){
if(arr[i]==0 and oth.arr[i]==1 ) return true;
if(arr[i]==1 and oth.arr[i]==0 ) return false;
}
return false;
}
bool operator<=( int512& oth){return *this<oth or !(oth<*this);}
};
bool ze=0;
const int mk=100;
int512 dp[mk][256], pr[mk][256];
void init(){
if(ze) return;
loop(i, 0, 256) dp[0][i]=int512(1);
loop(i, 1, mk) {
dp[i][0]=int512(1);
loop(j, 1, 256) dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
loop(i, 0, mk){
loop(j, 0, 256) pr[i][j]=dp[i][j];
loop(j, 1, 256) pr[i][j]=pr[i][j] + pr[i][j-1];
//loop(j, 0, 256) cout << pr[i][j].arr.to_ulong()<<" ";
//cout << endl;
}
ze=1;
}
vc<int> encode(int n, int m[]){
init();
int512 a(n, m);
int myk;
loop(i, 0, mk) if(a<=pr[i][255]) {myk=i;break;}
vc<int> ans;
pool(k, myk+1, 0){
loop(i, 0, 256) if(a<=pr[k][i]){ if(i!=0) a=a-pr[k][i-1];break;ans.ps(i);}
}
reverse(all(ans));
return ans;
}
void decode(int n, int l, int k[]){
sort(k, k+l);
int512 ans;
loop(i, 0, l) ans= ans+dp[i][k[i]];
ans=ans - int512(1);
for(int i=0;i<512;i+=8){
ll cans=0;
loop(j, 0, 8) cans+=(1<<j) * ans.arr[i+j];
cout << cans <<endl;
}
}
int main(){
//int512 a(3), b(5);
//cout << (a+b).arr.to_ulong()<<endl;
//init();
int m[3]={10, 30, 20};
auto ans=encode(3, m);
cout << ans.size()<<endl;
int bla[ans.size()];
loop(i, 0, ans.size()) bla[i]=ans[i];
decode(3, ans.size(), bla);
}