이번엔진짜F풀수있었는데이번엔진짜F풀수있었는데더어려운것도전에풀었는데더어려운것도전에풀었는데더어려운것도전에풀었는데
속도는 충분하다. 옐로우 찍히는 문제들을 쭉 돌다보면 F도 잘 되겠지
A
ABC찾기
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
#define debug(x) cout<< #x << " is " << x << "\n"
typedef long long ll;
int main(){
fast;
ll n,m,k;
string s,t;
vector<ll> v,e;
cin>>n>>s;
for(int i = 0 ; i < s.size()-2 ; i++){
if(s[i]=='A' and s[i+1] == 'B' and s[i+2]=='C')return cout<<i+1,0;
}
cout<<-1;
}
B
prefix suffix 확인
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
#define debug(x) cout<< #x << " is " << x << "\n"
typedef long long ll;
bool prefix(string s, string t){
if(s.size()>t.size())return 0;
for(int i = 0 ; i < s.size() ; i++){
if(s[i] != t[i])return 0;
}
return 1;
}
bool suffix(string s, string t){
reverse(all(s)); reverse(all(t));
return prefix(s,t);
}
int main(){
fast;
ll n,m,k;
string s,t;
cin>>n>>m>>s>>t;
if(prefix(s,t) and suffix(s,t))return cout<<0,0;
if(prefix(s,t))return cout<<1,0;
if(suffix(s,t))return cout<<2,0;
cout<<3;
}
C
그냥 이분탐색
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
#define debug(x) cout<< #x << " is " << x << "\n"
typedef long long ll;
ll n, m;
vector<ll> v;
int main(){
fast;
cin>>n>>m;
v.resize(m);
for(auto &i : v)cin>>i;
for(int i = 0 ; i < n ; i++){
ll d = *lower_bound(all(v), i+1);
cout<<d-(i+1)<<"\n";
}
}
D (1틀)
1틀은 좀 어이가 없다. xcode에서는 잘 나오는데 xcode가 음수 인덱스나 그런것도 잘 처리해줘서 xcode에서 잘나오는게 실제론 틀린 코드인 경우가 가끔 있다. 쨌든 얘만 아니었으면 25분 5솔인데 너무 아쉽다. 물론 퍼포먼스가 크게 오르는건 아니어서 상관없다.
문제가 굉장히 더러운데 능력껏 간단히 구현하면 된다.
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
#define debug(x) cout<< #x << " is " << x << "\n"
typedef long long ll;
ll arr[5][5];
string s[3][4];
void rot(ll a){
string res[4];
for(int i = 0 ; i < 4 ; i++)for(int j = 0 ; j < 4 ; j++)res[i][j] = s[a][4-j-1][i];
for(int i = 0 ; i < 4 ; i++)for(int j = 0 ; j < 4 ; j++)s[a][i][j] = res[i][j];
}
bool safe(ll x, ll y){
if(x<0 or y<0 or x>3 or y>3)return 0;
return 1;
}
bool c(ll x, ll y, ll a, ll t){
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
if(!safe(x+i,y+j)){
if(s[a][i][j] == '#')return 0;
}
}
}
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
if(s[a][i][j]=='#')arr[x+i][y+j] += t;
}
}
return 1;
}
void backtrack(ll x){
if(x==3){
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
if(arr[i][j]!=1)return;
}
}
cout<<"Yes\n";
exit(0);
}
for(int i = 0 ; i < 5 ; i++){
rot(x);
for(int j = -4 ; j <= 4 ; j++){
for(int k = -4 ; k <= 4 ; k++){
if(c(j,k,x,1)){
backtrack(x+1);
c(j,k,x,-1);
}
}
}
}
}
int main(){
fast;
for(int i = 0 ; i < 3 ; i++){
for(int j = 0 ; j < 4 ; j++)cin>>s[i][j];
}
backtrack(0);
cout<<"No";
}
E
5진수 비트마스킹 dp를 짜주면 된다.
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
#define debug(x) cout<< #x << " is " << x << "\n"
typedef long long ll;
ll n, m, p, k;
ll dp[6][6][6][6][6][101];
vector<ll> v[101];
ll f(ll a, ll b, ll c, ll d, ll e, ll x){
a = min(a,p); b = min(b,p); c = min(c,p); d = min(d,p); e = min(e,p);
if(a==p and b==p and c==p and d==p and e==p)return 0;
if(x==n)return 1e18;
ll &ret = dp[a][b][c][d][e][x];
if(~ret)return ret; ret = f(a,b,c,d,e,x+1);
ll A[5] = {a,b,c,d,e};
for(int i = 0 ; i < k ; i++)A[i] += v[x][i];
ret = min(ret, f(A[0],A[1],A[2],A[3],A[4],x+1)+v[x][k]);
return ret;
}
int main(){
fast;
cin>>n>>k>>p;
for(int i = 0 ; i < n ; i++){
ll c; cin>>c;
v[i].resize(k);
for(auto &j : v[i])cin>>j;
v[i].push_back(c);
}
memset(dp,-1,sizeof(dp));
ll A[5] = {0,0,0,0,0};
for(int i = k ; i < 5 ; i++)A[i] = p;
memset(dp,-1,sizeof(dp));
ll ans = f(A[0],A[1],A[2],A[3],A[4],0);
if(ans>=1e18)return cout<<-1,0;
else cout<<ans;
}
upsolving
F
레이지 금광세그를 짜주면 아마도 된다. 근데 금광세그 짜기 귀찮아서 이 문제에 제출한 코드를 복붙하고 레이지만 추가하고 있었는데 내가 내 코드를 해석을 못해서(...) 디버깅에 실패했다. 끝나기 4분전에 알았는데 아예 레이지를 잘못 짜고 있었다.
복붙한 금광세그는 아래 코드이다.
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, q;
typedef tuple<ll,ll,ll> T;
const tuple<ll,ll,ll> no = {-1e18,0,0};
bool f;
T merge(T a, T b){
auto [d1, siz1, idx1] = a;
auto [d2, siz2, idx2] = b;
if(d1!=d2){
if(d1>d2){
return {d1,siz1,idx1};
}
else return {d2,siz2,idx2};
}
else{
if(siz1<siz2){
if(idx1+siz1==idx2){
f=1;
siz2 += siz1;
idx2 = idx1;
}
return {d2,siz2,idx2};
}
else{
if(idx1+siz1==idx2){
f=0;
siz1 += siz2;
}
return {d1,siz1,idx1};
}
}
}
bool cmp(T a, T b){//a>b?
auto [x,y,z] = a;
auto [x2,y2,z2] = b;
if(x==x2){
if(y==y2)return z<z2;
return y>y2;
}
return x>x2;
}
struct segtree{
vector<tuple<T,T,T>> tree;
segtree(): tree(1212121) {}
void upd(ll node, ll s, ll e, ll idx, ll diff){
if(idx<s or e<idx)return;
if(s==e)tree[node] = {{diff,1,idx},{diff,1,idx},{diff,1,idx}};
else{
ll mid = s+e>>1;
upd(node*2,s,mid,idx,diff); upd(node*2+1,mid+1,e,idx,diff);
auto [a,b,c] = tree[node*2];
auto [D,E,F] = tree[node*2+1];
auto &[g,h,i] = tree[node];
auto [d1, siz1, idx1] = c;
auto [d2, siz2, idx2] = E;
g = merge(a,D);
auto [D1,Siz1,Idx1] = b;
auto [D2,Siz2,Idx2] = F;
if(Idx1+Siz1==idx2)h = merge(b,E);
else h = b;
if(idx1+siz1==Idx2)i = merge(c,F);
else i = F;
if(idx1+siz1==idx2){
if(cmp(merge(c,E),g))g = merge(c,E);
}
if(cmp(h,g))g=h;
if(cmp(i,g))g=i;
}
}
} seg;
int main(){
fast;
cin>>n;
for(int i = 1 ; i <= n ; i++){
ll a; cin>>a; seg.upd(1,1,n,i,a);
}
cin>>q;
while(q--){
ll a,b; cin>>a>>b;
seg.upd(1,1,n,a,b);
auto [A,B,c] = seg.tree[1];
auto [diff,siz,idx] = A;
cout<<idx<<" "<<idx+siz-1<<"\n";
}
}솔직히 이정도면 디버깅 못할만하다.
+) 아침에 조금만 바꿨더니 풀렸다....
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef int ll;
ll n, q;
typedef tuple<ll,ll,ll> T;
const tuple<ll,ll,ll> no = {-1e9,0,0};
bool f;
T merge(T a, T b){
auto [d1, siz1, idx1] = a;
auto [d2, siz2, idx2] = b;
if(d1!=d2){
if(d1>d2){
return {d1,siz1,idx1};
}
else return {d2,siz2,idx2};
}
else{
if(siz1<siz2){
if(idx1+siz1==idx2){
f=1;
siz2 += siz1;
idx2 = idx1;
}
return {d2,siz2,idx2};
}
else{
if(idx1+siz1==idx2){
f=0;
siz1 += siz2;
}
return {d1,siz1,idx1};
}
}
}
bool cmp(T a, T b){//a>b?
auto [x,y,z] = a;
auto [x2,y2,z2] = b;
if(x==x2){
if(y==y2)return z<z2;
return y>y2;
}
return x>x2;
}
struct segtree{
vector<tuple<T,T,T>> tree, tree2;
vector<bool> lazy;
segtree(): tree(2020202), tree2(2020202), lazy(2020202,0){}
void prop(ll node, ll s, ll e){
if(!lazy[node])return;
swap(tree[node],tree2[node]);
lazy[node]=0;
if(s^e)lazy[node*2]=!lazy[node*2], lazy[node*2+1]=!lazy[node*2+1];
}
void wow(ll node){
auto [a,b,c] = tree2[node*2];
auto [D,E,F] = tree2[node*2+1];
auto &[g,h,i] = tree2[node];
auto [d1, siz1, idx1] = c;
auto [d2, siz2, idx2] = E;
g = merge(a,D);
auto [D1,Siz1,Idx1] = b;
auto [D2,Siz2,Idx2] = F;
if(Idx1+Siz1==idx2)h = merge(b,E);
else h = b;
if(idx1+siz1==Idx2)i = merge(c,F);
else i = F;
if(idx1+siz1==idx2){
if(cmp(merge(c,E),g))g = merge(c,E);
}
if(cmp(h,g))g=h;
if(cmp(i,g))g=i;
}
void upd(ll node, ll s, ll e, ll idx, ll diff){
if(idx<s or e<idx)return;
if(s==e){
tree[node] = {{diff,1,idx},{diff,1,idx},{diff,1,idx}};
tree2[node] = {{!diff,1,idx},{!diff,1,idx},{!diff,1,idx}};
}
else{
ll mid = s+e>>1;
upd(node*2,s,mid,idx,diff); upd(node*2+1,mid+1,e,idx,diff);
wow(node);
auto [a,b,c] = tree[node*2];
auto [D,E,F] = tree[node*2+1];
auto &[g,h,i] = tree[node];
auto [d1, siz1, idx1] = c;
auto [d2, siz2, idx2] = E;
g = merge(a,D);
auto [D1,Siz1,Idx1] = b;
auto [D2,Siz2,Idx2] = F;
if(Idx1+Siz1==idx2)h = merge(b,E);
else h = b;
if(idx1+siz1==Idx2)i = merge(c,F);
else i = F;
if(idx1+siz1==idx2){
if(cmp(merge(c,E),g))g = merge(c,E);
}
if(cmp(h,g))g=h;
if(cmp(i,g))g=i;
}
}
void flip(ll node, ll s, ll e, ll l, ll r){
prop(node,s,e);
if(e<l or r<s)return;
if(l<=s and e<=r){
swap(tree[node],tree2[node]);
if(s^e)lazy[node*2]=!lazy[node*2], lazy[node*2+1]=!lazy[node*2+1];
return;
}
ll mid = s+e>>1;
flip(node*2,s,mid,l,r); flip(node*2+1,mid+1,e,l,r);
wow(node);
auto [a,b,c] = tree[node*2];
auto [D,E,F] = tree[node*2+1];
auto &[g,h,i] = tree[node];
auto [d1, siz1, idx1] = c;
auto [d2, siz2, idx2] = E;
g = merge(a,D);
auto [D1,Siz1,Idx1] = b;
auto [D2,Siz2,Idx2] = F;
if(Idx1+Siz1==idx2)h = merge(b,E);
else h = b;
if(idx1+siz1==Idx2)i = merge(c,F);
else i = F;
if(idx1+siz1==idx2){
if(cmp(merge(c,E),g))g = merge(c,E);
}
if(cmp(h,g))g=h;
if(cmp(i,g))g=i;
}
tuple<T,T,T> query(ll node, ll s, ll e, ll l, ll r){
prop(node,s,e);
if(e<l or r<s)return {no,no,no};
if(l<=s and e<=r)return tree[node];
ll mid = s+e>>1;
auto [a,b,c] = query(node*2,s,mid,l,r);
auto [D,E,F] = query(node*2+1,mid+1,e,l,r);
auto g=no,h=no,i=no;
auto [d1, siz1, idx1] = c;
auto [d2, siz2, idx2] = E;
g = merge(a,D);
auto [D1,Siz1,Idx1] = b;
auto [D2,Siz2,Idx2] = F;
if(Idx1+Siz1==idx2)h = merge(b,E);
else h = b;
if(idx1+siz1==Idx2)i = merge(c,F);
else i = F;
if(idx1+siz1==idx2){
if(cmp(merge(c,E),g))g = merge(c,E);
}
if(cmp(h,g))g=h;
if(cmp(i,g))g=i;
return {g,h,i};
}
} seg;
int main(){
fast;
cin>>n>>q;
for(int i = 1 ; i <= n ; i++){
char c; cin>>c;
ll a = (c == '1' ? 1 : 0);
seg.upd(1,1,n,i,a);
}
while(q--){
ll a,b,c; cin>>a>>b>>c;
if(a==1)seg.flip(1,1,n,b,c);
else{
auto [A,B,d] = seg.query(1,1,n,b,c);
auto [diff,siz,idx] = A;
if(diff==0)cout<<"0\n";
else cout<<siz<<"\n";
}
}
}