이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <vector>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef short int si;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef vector<v2i> v3i;
typedef vector<si> vs;
typedef vector<vs> v2s;
typedef vector<v2s> v3s;
#define pb push_back
#define rep(i, n) for (int i=0; i<n; i++)
int i = 0;
int r = 0;
int N = 0;
int minp3 = 0;
v2s trinum, upt, ept;
v3s cid;
v3i re;
void initialize(int n) {
N = n;
r = n*(n-1) / 2;
int s = 1;
while (s < n) {
minp3++;
s *= 3;
}
re.resize(minp3);
cid.resize(minp3);
trinum.resize(minp3);
upt.resize(minp3);
ept.resize(minp3);
// setting up trinum, cid
// cout << "Setting up trinum, cid... ";
rep(c, n) {
s = 1;
rep(j, minp3) {
s*=3;
int tnum = floor(c/s);
trinum[j].pb(tnum);
cid[j].resize(tnum + 1);
cid[j][tnum].pb(c);
}
}
/*cout << "done\ncID:\n";
for (auto tmp : cid) {
for (auto tmp2 : tmp) {
cout << tmp2.size() << " ";
}
cout << "\n";
}*/
// setting up ept, upt
//cout << "Setting up ept, upt... ";
s = 1;
rep(j, minp3) {
s *= 3;
upt[j].resize(cid[j].size(), 0);
int ptr = 0;
while (ptr < n) {
ept[j].pb(floor((min(s, n - ptr)*3 - 1)/s) + 1);
ptr += s;
}
}
/*cout << "done\nept:\n";
for (auto tmp : ept) {
for (auto tmp2 : tmp) {
cout << tmp2 << " ";
}
cout << "\n";
}*/
//setting up re
//cout << "Setting up re\n";
rep(j, minp3) {
re[j].resize(cid[j].size());
rep(k, cid[j].size()) {
if (j == 0) {
if (ept[j][k] == 3) re[j][k].resize(3, 1);
else if (ept[j][k] == 2) re[j][k].resize(ept[j][k]-1, 1);
} else {
if (ept[j][k] == 3) {
re[j][k].pb(cid[j-1][3*k].size()*cid[j-1][3*k + 1].size());
re[j][k].pb(cid[j-1][3*k + 1].size()*cid[j-1][3*k + 2].size());
re[j][k].pb(cid[j-1][3*k + 2].size()*cid[j-1][3*k].size());
} else if (ept[j][k] == 2) {
re[j][k].pb(cid[j-1][3*k].size()*cid[j-1][3*k + 1].size());
}
}
//cout << "Finished setting up re[" << j << "][" << k << "]\n";
}
//cout << "Finished setting up re[" << j << "]\n";
}
/*cout << "re:\n";
for (auto tmp : re) {
for (auto tmp2 : tmp) {
cout << "{";
for (auto tmp3 : tmp2) {
cout << tmp3 << ",";
}
cout << "} ";
}
cout << "\n";
}*/
}
int hasEdge(int u, int v) {
i++;
if (v<u) swap(u,v);
int l = 0; // lvl of the original triangle
while (trinum[l][u] != trinum[l][v]) l++;
//cout << "tri level of both cities is " << l;
int t = trinum[l][u];
//cout << "\ntri id is " << t << "\n";
if (l == 0) {
return ++upt[l][t] > 1 || ept[l][t] < 3;
} else {
int tu = trinum[l-1][u];
int tv = trinum[l-1][v];
//cout << tu << " " << tv << "\n";
int renum = (1 - (tu + tv - 6*t)) % 3;
//cout << "renum is " << renum << "\n";
//cout << "remaining edges between tris: " << re[l][t][renum] << "\n";
if (ept[l][t] < 2 || --re[l][t][renum] == 0) {
return ++upt[l][t] > 1 || ept[l][t] < 3;
} else return 0;
}
}
컴파일 시 표준 에러 (stderr) 메시지
game.cpp: In function 'void initialize(int)':
game.cpp:20:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | #define rep(i, n) for (int i=0; i<n; i++)
......
88 | rep(k, cid[j].size()) {
| ~~~~~~~~~~~~~~~~
game.cpp:88:9: note: in expansion of macro 'rep'
88 | rep(k, cid[j].size()) {
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |