QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #387679 | #6728. To the Park | Mayuri | AC ✓ | 85ms | 21320kb | C++14 | 15.8kb | 2024-04-12 18:34:16 | 2024-04-12 18:34:16 |
Judging History
answer
//#define _CRT_SECURE_NO_WARNINGS
////#include<bits/stdc++.h>
////using namespace std;
////typedef long long ll;
////typedef long double ld;
////#define endl '\n'
////const ll mod = 1e9 + 7;
////ll T;
////ll l, r;
////ll f(ll x) {
//// ll ans = 1;
//// while (x) {
//// ans = ans * (x % 10) % mod;
//// x /= 10;
//// }
//// return ans;
////}
////int main()
////{
//// ios::sync_with_stdio(0);
//// cin.tie(0);
//// cout.tie(0);
//// ll T; cin >> T;
//// while (T--) {
//// cin >> l >> r;
//// if (l / 10 != r / 10) {
//// cout << 0 << endl;
//// continue;
//// }
//// ll ans = 1;
//// for (ll i = l; i <= r; i++)ans = (ans * f(i)) % mod;
//// cout << ans << endl;
//// }
////}
// WA
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll t;
//ll n, m;
//
//int main()//b
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll t; cin >> t;
// while (t--) {
// cin >> n >> m;
// vector<vector<char>>f(n + 1, vector<char>(m + 1));
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cin >> f[i][j];
// }
// }
// vector<vector<ll>>a(n + 1, vector<ll>(m + 1));
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cin >> a[i][j];
// }
// }
// vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, -1));
// vector<vector<ll>>scc(n + 1, vector<ll>(m + 1, -1));
// vector<ll> sz(n * m + 1);
// ll cnt = 0;
// function<void(ll, ll)> fdfs = [&](ll x, ll y) -> void {
// if (x <= 0 || y <= 0 || x > n || y >m) {
// sz[cnt] = 0;
// return;
// }
// if (scc[x][y] != -1)return;
// scc[x][y] = cnt;
// sz[cnt]++;
// ll dx = 0, dy = 0;
// if (f[x][y] == 'l')dx = 0, dy = -1;
// if (f[x][y] == 'u')dx = -1, dy = 0;
// if (f[x][y] == 'r')dx = 0, dy = 1;
// if (f[x][y] == 'd')dx = 1, dy = 0;
// fdfs(x + dx * a[x][y], y + dy * a[x][y]);
// };
// function<ll(ll, ll)> dfs = [&](ll x, ll y) -> ll {
// if (x < 0 || y < 0 || x > n || y >m)return 0;
// ll& ans = dp[x][y];
// if (sz[scc[x][y]] != 0) {
// return ans = sz[scc[x][y]];
// }
// if (ans != -1)return ans;
// ans = 0;
// ll dx = 0, dy = 0;
// if (f[x][y] == 'l')dx = 0, dy = -1;
// if (f[x][y] == 'u')dx = -1, dy = 0;
// if (f[x][y] == 'r')dx = 0, dy = 1;
// if (f[x][y] == 'd')dx = 1, dy = 0;
// ans = dfs(x + dx * a[x][y], y + dy * a[x][y]) + 1;
// //cout << x << " " << y << " " << ans << endl;
// return ans;
// };
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// if (scc[i][j] == -1) {
// cnt++;
// fdfs(i, j);
// }
// }
// }
// ll ans = 0;
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// ans = max(ans, dfs(i, j));
// //cout << dfs(i, j) << " ";
// }//cout << endl;
// }
// if (ans == n * m) {
// cout << "yes" << endl;
// }
// else cout << "no" << endl;
// }
//}
// AC
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll T;
//ll n, m;
//int main()//B
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// cin >> n >> m;
// vector<vector<char>>f(n + 1, vector<char>(m + 1));
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cin >> f[i][j];
// }
// }
// vector<vector<ll>>a(n + 1, vector<ll>(m + 1));
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cin >> a[i][j];
// }
// }
// vector<vector<ll>>c(n + 1, vector<ll>(m + 1));
// for (ll x = 1; x <= n; x++) {
// for (ll y = 1; y <= m; y++) {
// ll dx = 0, dy = 0;
// if (f[x][y] == 'l')dx = 0, dy = -1;
// if (f[x][y] == 'u')dx = -1, dy = 0;
// if (f[x][y] == 'r')dx = 0, dy = 1;
// if (f[x][y] == 'd')dx = 1, dy = 0;
// ll tx = x + dx * a[x][y], ty = y + dy * a[x][y];
// if (tx < 0 || ty < 0 || tx > n || ty >m)continue;
// c[tx][ty]++;
// }
// }
// ll bx = 1, by = 1;
// for (ll x = 1; x <= n; x++) {
// for (ll y = 1; y <= m; y++) {
// if (c[x][y] == 0) {
// bx = x;
// by = y;
// }
// }
// }
// vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
// function<void(ll, ll)> dfs = [&](ll x, ll y) -> void {
// if (x <= 0 || y <= 0 || x > n || y >m)return;
// if (dp[x][y])return;
// dp[x][y] = true;
// ll dx = 0, dy = 0;
// if (f[x][y] == 'l')dx = 0, dy = -1;
// if (f[x][y] == 'u')dx = -1, dy = 0;
// if (f[x][y] == 'r')dx = 0, dy = 1;
// if (f[x][y] == 'd')dx = 1, dy = 0;
// dfs(x + dx * a[x][y], y + dy * a[x][y]);
// };
// bool flag = true;
// dfs(bx, by);
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// //cout << dp[i][j] << " ";
// if (!dp[i][j])flag = false;
// }//cout << endl;
// }
// if (flag) {
// cout << "Yes" << endl;
// }
// else cout << "No" << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll T;
//ll n, m;
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// cin >> n >> m;
// vector<vector<char>>f(n + 1, vector<char>(m + 1));
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cin >> f[i][j];
// }
// }
// vector<vector<ll>>a(n + 1, vector<ll>(m + 1));
// for (ll i = 1; i <= n; i++) {
// for (ll j = 1; j <= m; j++) {
// cin >> a[i][j];
// }
// }
// vector<vector<ll>>c(n + 1, vector<ll>(m + 1));
// for (ll x = 1; x <= n; x++) {
// for (ll y = 1; y <= m; y++) {
// ll dx = 0, dy = 0;
// if (f[x][y] == 'l')dx = 0, dy = -1;
// if (f[x][y] == 'u')dx = -1, dy = 0;
// if (f[x][y] == 'r')dx = 0, dy = 1;
// if (f[x][y] == 'd')dx = 1, dy = 0;
// ll tx = x + dx * a[x][y], ty = y + dy * a[x][y];
// if (tx < 0 || ty < 0 || tx > n || ty >m)continue;
// c[tx][ty]++;
// }
// }
// ll bx = 1, by = 1;
// for (ll x = 1; x <= n; x++) {
// for (ll y = 1; y <= m; y++) {
// if (c[x][y] == 0) {
// bx = x;
// by = y;
// }
// }
// }
// vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, -1));
// function<ll(ll, ll)> dfs = [&](ll x, ll y) -> ll {
// if (x <= 0 || y <= 0 || x > n || y >m)return 0;
// ll& ans = dp[x][y];
// if (ans != -1)return ans;
// ans = 0;
// ll dx = 0, dy = 0;
// if (f[x][y] == 'l')dx = 0, dy = -1;
// if (f[x][y] == 'u')dx = -1, dy = 0;
// if (f[x][y] == 'r')dx = 0, dy = 1;
// if (f[x][y] == 'd')dx = 1, dy = 0;
// ans = dfs(x + dx * a[x][y], y + dy * a[x][y]) + 1;
// //cout << x << " " << y << " " << ans << endl;
// return ans;
// };
// bool flag = true;
// if (dfs(bx, by) != n * m)flag = false;
// if (flag) {
// cout << "Yes" << endl;
// }
// else cout << "No" << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll T;
//ll n, m;
//ll x, y, z;
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// cin >> x >> y >> z;
// ll d = x + y - z;
// if (d == 0)cout << (ll)1e9 << endl;
// else if (d <= z || y < z)cout << -1 << endl;
// else cout << d << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll T;
//ll n, k;
//string s;
//bool check(ll x) {
// ll cnt = 0;
// for (ll i = 0; i < s.size(); i++) {
// if (s[i] == '1') {
// if (x == 0)return false;
// cnt++;
// i += x - 1;
// }
// }
// return cnt <= k;
//}
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// cin >> n >> k;
// cin >> s;
// ll l = -1, r = 2e5 + 5;
// while (l < r - 1) {
// ll mid = (l + r) >> 1;
// if (check(mid)) r = mid;
// else l = mid;
// }
// cout << r << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll T;
//int main()//C读错
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// string s; cin >> s;
// ll now = 0;
// ll cnt = 0;
// ll ans = 0;
// for (ll i = 0; i < s.size(); i++) {
// if (now == 0) {
// if (s[i] == '6' || s[i] == '9') now = 2, cnt = 1;
// else if (s[i] == '8' || s[i] == '0') now = 1, cnt = 1;
// else now = 0, cnt = 0;
// }
// else {
// cnt++;
// if(s[i] == '6' || s[i] == '9') now = now * 2 * cnt;
// else if(s[i] == '8' || s[i] == '0') now = now * cnt;
// else {
// ans += now;
// now = 0, cnt = 0;
// }
// }
// cout << now << " " << cnt << endl;
// }
// ans += now;
// cout << ans << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//ll T;
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// string s; cin >> s;
// ll now = 0;
// ll cnt = 0;
// ll ans = 0;
// for (ll i = 0; i < s.size(); i++) {
//
// }
// ans += now;
// cout << ans << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//const ll maxn = 2e5 + 5;
//ll T;
//ll n;
//ll l[maxn], r[maxn];
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// cin >> n;
// for (ll i = 1; i <= n; i++) cin >> l[i] >> r[i];
// ll ans = 0;
// vector<ll>bas(n + 1);
// vector<bool>pass(n + 1);
// for (ll i = 32; i >= 0; i--) {
// bool flag = true;
// for (ll j = 1; j <= n; j++) {
// if (pass[j])continue;
// ll L = (1ll << i) + bas[j], R = (1ll << (i + 1)) - 1 + bas[j];
// if (l[j] > R || r[j] < L) flag = false;
// }
// if (flag) {
// for (ll j = 1; j <= n; j++) {
// bas[j] += 1ll << i;
// }
// ans += 1ll << i;
// }
// else {
// for (ll j = 1; j <= n; j++) {
// ll t = (1ll << i) - 1 + bas[j];
// if (l[j] <= t && r[j] >= t)pass[j] = true;
// else {
// if (r[j] < t)continue;
// else {
// bas[j] += 1ll << i;
// }
// }
// }
// }
// }
// cout << ans << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//const ll maxn = 2e5 + 5;
//ll T;
//ll n;
//ll l[maxn], r[maxn];
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// string s;
// cin >> s;
// vector<string>v;
// string now;
// ll ans = 0;
// for (ll i = 0; i < s.size(); i++) {
// if (s[i] == '6' || s[i] == '9' || s[i] == '8' || s[i] == '0') now += s[i];
// else {
// if (now.size())v.push_back(now);
// now.clear();
// }
// }
// if (now.size())v.push_back(now);
// ll flag = 0;
// for (auto it : v) {
// vector<ll>c(15);
// ans += it.size() * (it.size() - 1) / 2;
// for (ll i = 0; i < it.size(); i++) {
// ll t = it[i] - '0';
// if (t == 6 || t == 9)ans++;
// if (t == 0 || t == 8)flag = 1;
// if (i > 0) {
// if (it[i] == '6' && it[i - 1] == '9')flag = 1;
// if (it[i] == '9' && it[i - 1] == '6')flag = 1;
// }
// if (t == 6)ans -= c[9];
// else if (t == 9)ans -= c[6];
// else if (t == 8)ans -= c[8];
// else if (t == 0)ans -= c[0];
// c[t]++;
// }
// }
// ans += flag;
// cout << ans << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//const ll maxn = 2e5 + 5;
//ll T;
//ll n;
//ll ecnt = 0;
//ll head[maxn];
//ll to[maxn << 1];
//ll nxt[maxn << 1];
//char w[maxn << 1];
//bool vis[maxn << 1];
//bool dp[maxn << 1];
//void add(ll u, ll v, char ch) {
// ++ecnt;
// w[ecnt] = ch;
// nxt[ecnt] = head[u];
// to[ecnt] = v;
// head[u] = ecnt;
//}
//void clear() {
// for (ll i = 1; i <= n; i++)head[i] = 0;
// for (ll i = 1; i <= ecnt; i++)vis[i] = false;
// ecnt++;
//}
//bool is[maxn];
//bool dfs(ll u, ll fa) {
// bool flag = true;
// char ch = '#';
// for (ll i = head[u]; i; i = nxt[i]) {
// ll v = to[i];
// if (fa == v)continue;
// if (ch == w[i])flag = false;
// ch = w[i];
// if (!vis[i]) {
// vis[i] = true;
// dp[i] &= dfs(v, u);
// }
// flag &= dp[i];
// }
// return flag;
//}
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// ll T; cin >> T;
// while (T--) {
// clear();
// cin >> n;
// for (ll i = 1; i <= n - 1; i++) {
// ll u, v; char ch;
// cin >> u >> v >> ch;
// add(u, v, ch);
// add(v, u, ch);
// }
// ll ans = 0;
// for (ll i = 1; i <= n; i++) if (dfs(i, 0))ans++;
// cout << ans << endl;
// }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//typedef long double ld;
//#define endl '\n'
//const ll mod = 1e9 + 7;
//const ll maxn = 1e5 + 5;
//ll T;
//ll n;
//vector<ll>p[maxn];
//void pre() {//埃氏筛处理因子表
// for (ll i = 1; i < maxn; i++) {
// for (ll j = 1; i * j < maxn; j++) {
// p[i * j].push_back(j);
// }
// }
//}
//int main()
//{
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
// pre();
// ll T; cin >> T;
// while (T--) {
// cin >> n;
// vector<bool>is(n + 1);
// vector<pair<ll, ll>>ans;
// is[1] = true;
// for (ll i = n; i >= 1; i--) {
// if (is[i])continue;
// //for (ll j = 2; j <= sqrt(i + 0.5); j++) {
// // if (i % j == 0 && !is[j]) {
// // ans.push_back({ j, i });
// // is[i] = is[j] = true;
// // break;
// // }
// //}
// for(auto j:p[i]){
// if (j == i)continue;
// if (!is[j]) {
// ans.push_back({ j, i });
// is[i] = is[j] = true;
// break;
// }
// }
// }
// cout << ans.size();
// for (auto it : ans)cout << " " << it.first << " " << it.second;
// cout << endl;
// }
//}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 5;
ll T;
ll n;
vector<ll>p[maxn];
void pre() {//埃氏筛处理因子表
for (ll i = 1; i < maxn; i++) {
for (ll j = 1; i * j < maxn; j++) {
p[i * j].push_back(j);
}
sort(p[i].begin(), p[i].end());
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
pre();
ll T; cin >> T;
while (T--) {
cin >> n;
vector<bool>is(n + 1);
vector<ll>ans;
is[1] = true;
for (ll i = 3; i <= n; i++) {
vector<ll>tem;
for (ll j = 1; j * i <= n; j++) {
if (is[i * j])continue;
tem.push_back(j * i);
}
if (tem.size() > 1) {
if (tem.size() & 1) {
for (auto it : tem) {
if (it == i * 2)continue;
ans.push_back(it);
is[it] = true;
}
}
else {
for (auto it : tem) {
ans.push_back(it);
is[it] = true;
}
}
}
}
for (ll i = 2; i <= 2; i++) {
vector<ll>tem;
for (ll j = 1; j * i <= n; j++) {
if (is[i * j])continue;
tem.push_back(j * i);
}
if (tem.size() & 1) {
for (auto it : tem) {
if (it == 2)continue;
ans.push_back(it);
is[it] = true;
}
}
else {
for (auto it : tem) {
ans.push_back(it);
is[it] = true;
}
}
}
cout << ans.size() / 2;
for (auto it : ans)cout << " " << it;
cout << endl;
}
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 38ms
memory: 19584kb
input:
3 1 4 6
output:
0 1 2 4 2 3 6 2 4
result:
ok 4 cases
Test #2:
score: 0
Accepted
time: 85ms
memory: 21320kb
input:
1007 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
0 0 0 1 2 4 1 2 4 2 3 6 2 4 2 3 6 2 4 2 3 6 4 8 3 3 9 4 8 2 6 4 3 9 4 8 5 10 2 6 4 3 9 4 8 5 10 2 6 4 3 6 9 12 4 8 5 10 4 3 6 9 12 4 8 5 10 5 3 6 9 12 4 8 5 10 7 14 6 3 9 12 15 4 8 5 10 7 14 2 6 6 3 9 12 15 4 16 5 10 7 14 6 8 6 3 9 12 15 4 16 5 10 7 14 6 8 7 3 6 9 12 15 18 4 16 5 10 7 14 2 8 7 3 6 9...
result:
ok 1008 cases