Submission #66738241

---

Source Code Expand

//include
// C++ includes used for precompiling -*- C++ -*-
// Copyright (C) 2003-2013 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.
/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */
// 17.4.1.2 Headers
// C
# ifndef _GLIBCXX_NO_ASSERT
# include <cassert>
# endif
# include <cctype>
# include <cerrno>
# include <cfloat>
# include <ciso646>
# include <climits>
# include <clocale>
# include <cmath>
# include <csetjmp>
# include <csignal>
# include <cstdarg>
# include <cstddef>
# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <ctime>
# if __cplusplus >= 201103L
# include <ccomplex>
# include <cfenv>
# include <cinttypes>
# include <cstdbool>
# include <cstdint>
# include <ctgmath>
# include <cwchar>
# include <cwctype>
# endif
// C++
# include <algorithm>
# include <bitset>
# include <complex>
# include <deque>
# include <exception>
# include <fstream>
# include <functional>
# include <iomanip>
# include <ios>
# include <iosfwd>
# include <iostream>
# include <istream>
# include <iterator>
# include <limits>
# include <list>
# include <locale>
# include <map>
# include <memory>
# include <new>
# include <numeric>
# include <ostream>
# include <queue>
# include <set>
# include <sstream>
# include <stack>
# include <stdexcept>
# include <streambuf>
# include <string>
# include <typeinfo>
# include <utility>
# include <valarray>
# include <vector>
# if __cplusplus >= 201103L
# include <array>
# include <atomic>
# include <chrono>
# include <condition_variable>
# include <forward_list>
# include <future>
# include <initializer_list>
# include <mutex>
# include <random>
# include <ratio>
# include <regex>
# include <scoped_allocator>
# include <system_error>
# include <thread>
# include <tuple>
# include <typeindex>
# include <type_traits>
# include <unordered_map>
# include <unordered_set>
# endif
//pragma
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//define
#define pb push_back 
#define pob pop_back
#define umap unordered_map
#define uset unordered_set
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define srep(i, s, n) for (int i = s; i < (int)(n); i++)
#define spe <<" "<< //space
#define sei fixed<<setprecision(20) //seido

//using,template
using namespace std;
using ll = long long;
using ld = long double;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using bl = bool;
using vl = vc<ll>; using vvl = vv<ll>; //Frest様より
using vvvl = vv<vl>; using vvvvl = vv<vvl>;
using vs = vc<string>; using vvs = vv<string>;
using vb = vc<bl>; using vvb = vv<bl>; using vvvb = vv<vb>;
using vld = vc<ld>; using vvld = vv<ld>; using vvvld = vv<vld>;
using P = pair<ll, ll>;
template<class T>istream& operator>>(istream& i, vc<T>& v) { rep(j, size(v))i >> v[j]; return i; }

//変数
ll INF=9e18;
ll mod=998244353;
ll mod2=1000000007;

//@gis様のQiita記事より
class Rand {
private:
	//32ビット版メルセンヌ・ツイスタ
	std::mt19937 mt;
	//非決定論的な乱数
	std::random_device rd;

public:
	//コンストラクタ(初期化)
	Rand() { mt.seed(rd()); }

	//初期値
	void seed() {
		mt.seed(rd());
	}
	void seed(const std::uint_fast32_t seed_) {
		mt.seed(seed_);
	}

	//通常の乱数
	std::uint_fast32_t operator()() {
		return mt();
	}
	//0～最大値-1 (余りの範囲の一様分布乱数)
	std::int_fast32_t operator()(const std::int_fast32_t max_) {
		std::uniform_int_distribution<> uid(0, ((max_ > 0) ? (std::int_fast32_t)max_ - 1 : 0));
		return uid(mt);
	}
	//最小値～最大値
	std::int_fast32_t operator()(const std::int_fast32_t min_, const std::int_fast32_t max_) {
		std::uniform_int_distribution<> uid((min_ <= max_) ? min_ : max_, (min_ <= max_) ? max_ : min_);
		return uid(mt);
	}
	//確率
	bool randBool(const double probability_) {
		std::bernoulli_distribution uid(probability_);
		return uid(mt);
	}
	bool randBool() {
		std::uniform_int_distribution<> uid(0, 1);
		return ((uid(mt)) ? true : false);
	}
};
static thread_local Rand rnd;

//AHC用タイマー Frest様より
class TimeKeeper {
private:
    std::chrono::high_resolution_clock::time_point start_time_;
    int64_t time_threshold_;

public:
    // 時間制限をミリ秒単位で指定してインスタンスをつくる。 1秒(s)=1000ms
    TimeKeeper(const int64_t& time_threshold)
        : start_time_(std::chrono::high_resolution_clock::now()),
        time_threshold_(time_threshold)
    {
    }

    // インスタンス生成した時から指定した時間制限を超過したか判定する。
    bool isTimeOver() const
    {
        auto diff = std::chrono::high_resolution_clock::now() - this->start_time_;
        return std::chrono::duration_cast<std::chrono::milliseconds>(diff).count() >= time_threshold_;
    }
    double get_time() {//経過時間を返す
        auto diff = std::chrono::high_resolution_clock::now() - this->start_time_;
        return std::chrono::duration_cast<std::chrono::milliseconds>(diff).count();
    }
};


int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;cin>>N;
  ll Q;cin>>Q;
  vl X;
  rep(i,Q){
    ll k;cin>>k;
    X.pb(k);
  }
	vl bx(N);
	rep(i,Q){
		if (X[i]!=0){
			bx[X[i]-1]++;
			cout<<X[i]<<" ";
		}
		else{
			ll mn=INF;
			ll idx=0;
			rep(j,N){
				if (bx[j]<mn){
					idx=j;
					mn=bx[j];
				}
			}
			bx[idx]++;
			cout<<idx+1<<" ";
		}
	}
}

Submission Info

Judge Result