제출 #255158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255158		shayan_p	popa (BOI18_popa)	C++14	100 / 100	109 ms	500 KiB

popa

// And you curse yourself for things you never done

#include "popa.h"

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1010, mod = 1e9 + 7, inf = 1e9 + 10;

int aft[maxn], bef[maxn];
/*
int S[maxn];

bool query(int l1, int r1, int l2, int r2){
    int g1 = 0, g2 = 0;
    while(l1 <= r1)
	g1 = __gcd(g1, S[l1]), l1++;
    while(l2 <= r2)
	g2 = __gcd(g2, S[l2]), l2++;
    return g1 == g2;
}
*/

int solve(int n, int *L, int *R){
    stack<int> st;
    for(int i = 0; i < n; i++){
	while(sz(st) && query(st.top(), i, i, i) )
	    aft[ st.top() ] = i, st.pop();
	bef[i] = (st.empty() ? -1 : st.top());
	st.push(i);
    }
    while(sz(st)){
	aft[st.top()] = n;
	st.pop();
    }   
    for(int i = 0; i < n; i++){
	L[i] = R[i] = -1;
    }
    int ans = -1;
    for(int i = 0; i < n; i++){
	if(bef[i] == -1 && aft[i] == n){
	    ans = i;
	    continue;
	}
	if(bef[i] == -1){
	    L[ aft[i] ] = i;
	    continue;
	}
	if(aft[i] == n){
	    R[ bef[i] ] = i;
	    continue;
	}
	if(bef[ aft[i] ] == bef[i]){
	    L[ aft[i] ] = i;
	}
	else{
	    R[ bef[i]]  = i;
	}
    }
    return ans;
}
/*
int L[maxn], R[maxn];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
	cin >> S[i];
    }
    cout << "HEY " << solve(n, L, R) << endl;
    for(int i = 0; i < n; i++){
	cout << L[i] << " " << R[i] << endl;
    }
    return 0;
}
*/

• Subtask 1: 37 / 37
• Subtask 2: 24 / 24
• Subtask 3: 39 / 39