Submission #774633

#	Time	Username	Problem	Language	Result	Execution time	Memory
774633		Antonn_114	Stone Arranging 2 (JOI23_ho_t1)	C++14	100 / 100	132 ms	39812 KiB

Main

#include <bits/stdc++.h>
using namespace std;

// Write down the limits of the problem here

inline void compress(vector<int> &a, unordered_map<int, int> &key){
    unordered_map<int, int> b;
    int n = a.size();
    for (int i = 0, t = 0; i < n; i++)
        if (b.find(a[i]) == b.end())
            key[t] = a[i], b[a[i]] = t++;
    for (int i = 0; i < n; i++)
        a[i] = b[a[i]];
}

int main() {
	// Try to avoid cin, cout :)

	int tc = 1; // scanf("%d", &tc);
	while(tc--) {
		/// Your solution here
	    int n;
        scanf("%d", &n);
        vector<int> a(n);
        vector<set<int>> b(n);
        for (auto &i : a) scanf("%d", &i);
        unordered_map<int, int> uncompress;
        compress(a, uncompress);
        for (int i = 0; i < n; i++) b[a[i]].insert(i);
        vector<int> res(n + 1);
        int ptr = 0;
        while (ptr < n){
            res[ptr] += a[ptr];
            res[(*b[a[ptr]].rbegin()) + 1] -= a[ptr];
            ptr = (*b[a[ptr]].rbegin()) + 1; 
        }
        for (int i = 1;i < n; i++){
            res[i] += res[i - 1];
        }
        for (int i = 0; i < n; i++){
            printf("%d\n", uncompress[res[i]]);
        }
		
	}
	return 0;
}

/*
 * Ermm don't underestimate Div2A, pls...
 * 
 * IMPORTANT:: If there isn't a clear-cut approach for your program, DO NOT CODE YET!
 * 
 * Analyze the time complexity and space complexity even if it *seems* efficient
 *
 * Write down some notes for more complicated problems
 * 
 * Also, please, CP isn't supposed to be complicated
 * 
**/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
Main.cpp:26:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         for (auto &i : a) scanf("%d", &i);
      |                           ~~~~~^~~~~~~~~~

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