| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1251764 | archso | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "souvenirs.h"
typedef long long ll;
using namespace std;
void buy_souvenirs(int n, long long p0){
if(n == 3){
pair<vector<int>,int> stuff = transaction(p0-1);
ll know = p0-1-stuff.second;
if(stuff.first == {1}){
// b
pair<vector<int>,int> morestuff = transaction(know-1);
ll kenow = know - 1 - morestuff.second;
if(morestuff.first == {2}){
transaction(kenow);
// c c
pair<vector<int>,int> finalstuff = transaction(kenow - 1);
ll finalknow = kenow - 1 - finalstuff.second;
transaction(finalknow);
transaction(finalknow);
// d d d
} else {
// c d
pair<vector<int>,int> finalstuff = transaction((kenow)/2);
// d
ll finalknow = (kenow)/2 - finalstuff.second;
ll otherknow = kenow - finalknow;
transaction(otherknow);
// c
transaction(finalknow);
// d
}
} else if(stuff.first == {1,2}) {
// b c
pair<vector<int>,int> morestuff = transaction(know / 2);
ll kenow = know / 2 - morestuff.second;
if(morestuff.first == {2}){
// c
// 3 * d
transaction(kenow-1);
transaction(kenow-1);
transaction(kenow-1);
} else {
// c d
// two d's
transaction((kenow)/2);
transaction((kenow)/2);
}
} else if(stuff.first == {1,3}) {
// b d
pair<vector<int>,int> morestuff = transaction(know / 2);
ll kenow = know / 2 - morestuff.second;
if(morestuff.first == {2}){
// b,c,d
// b,c,c,d
transaction(kenow);
// b,c,c,d,d,d
// :)
transaction(kenow-1);
transaction(kenow-1);
} else if(morestuff.first == {3}){
// b d d
// this stores what b is
// kenow has d
ll prevknow = know - kenow;
pair<vector<int>,int> evenmorestuff = transaction(prevknow-1);
ll finalknow = prevknow - 1- evenmorestuff.second;
if(evenmorestuff.size() == 1){
// b c d d
transaction(finalknow);
transaction(finalknow - 1);
// okay!
}
} else{
// b c d d
// just do it again!
transaction(know / 2);
}
} else {
// b c d
// on this branch
pair<vector<int>,int> morestuff = transaction(know/3);
ll kenow = know / 3 - morestuff.second;
if(morestuff.first == {2}) {
// b c c d
transaction(kenow-1);
transaction(kenow-1);
} else if(morestuff.first == {3}) {
// b c d d
// this holds b+c;
ll prevknow = know - kenow;
pair<vector<int>,int> evenmorestuff = transaction(prevknow / 2);
if(evenmorestuff.first == {2}){
// bccdd
transaction(kenow);
}
} else {
// b c c d d
transaction(kenow / 2);
}
}
}
else{
int amnt = 1;
long long curr = p0;
for(int i = 2; i < n; i++){
pair<vector<int>,int> stuff = transaction(curr-1);
if(stuff.first.size() == 2){
// multiple elements
// which has to be the last
amnt++;
curr-=2;
}
else{
// one element
curr -= (1+stuff.second);
}
for(int j = 2; j < i; j++){
transaction(curr);
}
}
// the last element has been queried a total of amnt times.
for(int i = amnt; i < n; i++){
transaction(curr-1);
}
}
}