Submission #790869

#	Time	Username	Problem	Language	Result	Execution time	Memory
790869		kwongweng	Newspapers (CEOI21_newspapers)	C++17	4 / 100	5 ms	2004 KiB

newspapers

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
ll MOD1 = 998244353;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD; b %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

ld pi = 3.141592653589793238;
/*
struct segtree{
	vector<ll> op, ans;
	int sz = 0;
	void init(int n){
		sz = n;
		op.assign(4*n, -1);
		ans.assign(4*n, 0);
	}
	void prop(int v, int tl, int tr){
		if (op[v] == -1 || tl == tr) return;
		int tm = (tl+tr)/2;
		op[2*v] = op[v];
		op[2*v+1] = op[v];
		ll len1 = tm-tl+1, len2 = tr-tm;
		ans[2*v] = op[v] * len1;
		ans[2*v+1] = op[v] * len2;
		op[v] = -1;
	}
	void update(int v, int tl, int tr, int l, int r, int val){
		prop(v, tl, tr);
		if (l > r) return;
		if (tl == l && tr == r){
			op[v] = val;
			ll len = tr-tl+1;
			ans[v] = val * len;
			return;
		}
		int tm = (tl+tr)/2;
		update(2*v, tl, tm, l, min(r,tm), val);
		update(2*v+1, tm+1, tr, max(l, tm+1), r, val);
		ans[v] = ans[2*v] + ans[2*v+1];
	}
	void update(int l, int r, int val){
		update(1, 0, sz-1, l, r, val);
	}
	ll get(int v, int tl, int tr, int l, int r){
		prop(v, tl, tr);
		if (l > r) return 0;
		if (tl == l && tr == r) return ans[v];
		int tm = (tl+tr)/2;
		ll m1 = get(2*v, tl, tm, l, min(r, tm));
		ll m2 = get(2*v+1, tm+1, tr, max(l, tm+1), r);
		return m1 + m2;
	}
	ll get(int l, int r){
		return get(1, 0, sz-1, l, r);
	}
}; 
*/
// adding up fractions
pll add(pll a, pll b){
	return {(a.fi*b.se + a.se*b.fi) % MOD, (a.se*b.se) % MOD};
}

int lis(vector<int> a) {
	vector<int> dp;
	int n = a.size();
	FOR(i,0,n){
		int pos = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
		if (pos == dp.size()) {
			dp.pb(a[i]);
		} else {
			dp[pos] = a[i];
		}
	}
	return dp.size();
}

const int N = 200001;
ll fact[N];

ll C(int n, int k){
	if (n<k || k<0) return 0;
	return mul(fact[n], inverse(mul(fact[k], fact[n-k])));
}

ll F(ll n){
	return (n*(n-1))/2;
}

ll phi(ll n){
	ll m = n;
	ll cur = 2;
	ll ans = 1;
	while (cur*cur <= m){
		if (m % cur == 0){
			ans *= (cur-1);
			m /= cur;
			while (m % cur == 0){
				m /= cur;
				ans *= cur;
			}
		}
		cur++;
	}
	if (m>1){
		ans *= (m-1);
	}
	return ans;
}

void solve(){
	int n, m; cin >> n >> m;
	vi g[n+1]; vi deg(n+1);
	FOR(i,0,m){
		int u, v; cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	/*
	if (m > n-1){
		cout << "NO\n";
		return;
	}
	FOR(i,1,n+1){
		if (deg[i]==1) continue;
		int cnt = 0;
		for (int u : g[i]){
			if (deg[u] >= 2) cnt++;
		}
		if (cnt >= 3){
			cout << "NO\n";
			return;
		}
	}
	*/
	cout << "YES\n";
	cout << 2*n << "\n";
	FOR(i,1,n+1){
		cout << i << " " << i << " ";
	}
	cout << "\n";
}

int main(){
	//MOD=MOD1;
	fact[0]=1; FOR(i,1,N) fact[i] = mul(fact[i-1],i);
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
	
	return 0;
}

Compilation message (stderr)

newspapers.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("Ofast")
      | 
newspapers.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
newspapers.cpp: In function 'int lis(std::vector<int>)':
newspapers.cpp:112:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   if (pos == dp.size()) {
      |       ~~~~^~~~~~~~~~~~
newspapers.cpp: In function 'int main()':
newspapers.cpp:192:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
newspapers.cpp:193:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 4 / 8
• Subtask 3: 0 / 80