Submission #1149542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149542		henriess	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	46 ms	15688 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast","inline","fast-math","unroll-loops","no-stack-protector","-ffast-math", "O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
 
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCC(t) scanf("%c",&t)
#define SCS(t) scanf("%s",t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define readInt(type) readInt<type>()
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long long int int64;
typedef unsigned long long int  uint64;
typedef vector<int64> VI64;
typedef vector<uint64> VUI64;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
#ifdef DEBUG
    #define debug(args...)     (Debugger()) , args
    class Debugger
    {
        public:
        Debugger(const string& _separator = " ") :
        first(true), separator(_separator){}
        template<typename ObjectType> Debugger& operator , (const ObjectType& v)
        {
            if(!first)
                cerr << separator;
            cerr << v;
            first = false;
            return *this;
        }
        ~Debugger() {  cerr << endl;}
        private:
        bool first;
        string separator;
    };
#else
    #define debug(args...) // Just strip off all debug tokens
#endif
// }}}
 
/********** Main() function **********/
int64 grid[512][512];
int Fx[100];
int Fy[100];
int64 next_grid[512][512];
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    
    vector<pair<int, long long>> seg;
    seg.reserve(N);
    
    unordered_map<int, int> pos;
    pos.reserve(N * 2);
    
    for (int i = 0; i < N; i++){
        int c = A[i];
        if(seg.empty()){
            seg.push_back({c, 1});
            pos[c] = 0;
        }
        else if(seg.back().first == c){
            seg.back().second++;
        }
        else if(pos.find(c) != pos.end()){
            int idx = pos[c];
            long long removedCount = 0;
            while((int)seg.size() > idx + 1){
                removedCount += seg.back().second;
                pos.erase(seg.back().first);
                seg.pop_back();
            }
            seg[idx].second += removedCount + 1;
        }
        else {
            seg.push_back({c, 1});
            pos[c] = seg.size() - 1;
        }
    }
        for (auto &p : seg) {
        int color = p.first;
        long long count = p.second;
        while(count--){
            cout << color << "\n";
        }
    }
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40